#include<bits/stdc++.h>
using namespace std;
int head[100000],cnt;
long long ans[1000000];
bool vis[100000];
int m,n,s;
struct edge
{
    int to;//当前数
    int nextt;//下一个数
    int wei;//距离
}edge[100000];
void addedge(int x,int y,int z)
{
    edge[++cnt].to=y;
    edge[cnt].wei=z;
    edge[cnt].nextt=head[x];
    head[x]=cnt;
}
int a,b,c;
int main(){
    cin>>m>>n>>s;
    for(int i=1;i<=n;i++)//初始化
        ans[i]=2147483647;
    ans[s]=0;
    int pos=s;
    for(int i=1;i<=n;i++)
        cin>>a>>b>>c,addedge(a,b,c);
    while(!vis[pos])//没有到最后
    {
        long long minn=2147483647;
        vis[pos]=1;
        for(int i=head[pos];i!=0;i=edge[i].nextt)
            if(!vis[edge[i].to]&&ans[edge[i].to]>ans[pos]+edge[i].wei)//下一个数不是最后&&有更优答案
                ans[edge[i].to]=ans[pos]+edge[i].wei;//更新答案
        for(int i=1;i<=m;i++)
            if(ans[i]<minn&&vis[i]==0)
                minn=ans[i],pos=i;//尝试更新

    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<" ";
    return 0;
}