#include<bits/stdc++.h>
using namespace std;
int n,m,s;
vector<int>grap[100009],len[100009];
int dis[100009],vis[10009];
int q[100009];
int spfa(int s)
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=2147483647;
    }
    dis[s]=0;
    vis[s]=1;
    int f,r;
    f=r=-1;
    q[++r]=s;
    while(f!=r)
    {
        f++;
        if(f==100009)f=0;
        int tmp=q[f];
        vis[tmp]=0;
        for(int i=0;i<grap[tmp].size();i++)
        {
            int nxt=grap[tmp][i];
            int cost=len[tmp][i];
            if(dis[tmp]+cost<dis[nxt])
            {
                dis[nxt]=dis[tmp]+cost;
                if(vis[nxt]==0)
                {
                    r++;
                    q[r]=nxt;
                    vis[nxt]=1;
                }
            }
        }
    }
}
int main()
{
   cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        grap[a].push_back(b);
        len[a].push_back(c);
    }
    spfa(s);
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<' ';
    }
    return 0;
}