#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m,s,u[N],v[N],w[N];
int dis[N],bis[N];
int main(){
    cin>>n>>m>>s;
    memset(dis,inf,sizeof(dis));
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
    dis[s]=0;
    for(int k=1;k<=n-1;k++){//n-1次
        int f=0;
        for(int i=1;i<=m;i++){
            if(dis[u[i]]==inf)continue;
            if(dis[v[i]]>dis[u[i]]+w[i])f=1,dis[v[i]]=dis[u[i]]+w[i];
        }
        if(f==0)break;
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==inf)cout<<(1<<31)-1<<" ";//说明不相连
        else cout<<dis[i]<<" ";
    }
    return 0;
}