#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
bool flag[100000];
int n,m,s,a[100000][100000],op1,op2,dis[100000];
int main(){
	freopen("main.in","r",stdin);
	freopen("main.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i][j]=inf;
    for(int i=0;i<m;i++){
        scanf("%d%d",&op1,&op2);
        scanf("%d",&a[op1-1][op2-1]);
    }
    flag[s]=true;
    for(int i=0;i<n;i++) dis[i]=a[s][i];
    for(int i=1;i<n;i++){
        for(int j=0;j<n;j++){
            op2=inf;
            if(!flag[j]&&dis[j]<op2){
                op2=dis[j];
                op1=j;
            }
        }
        flag[op1]=true;
        for(int j=0;j<n;j++){
            op2=(a[op1][j]==inf)?inf:dis[op1]+a[op1][j];
            if(!flag[j]&&op2<dis[j]) dis[j]=op2;
        }
    }
    for(int i=0;i<n;i++) printf("%d ",dis[i]);
    return 0;
}