#include <iostream>
#include <cstring>

using namespace std;

const int N=5e5+10,INF=0x3f3f;
int n,m,s;
int ne[N],e[N],h[N],w[N],idx;
int d[N];
bool st[N];

void init()
{
    memset(h,-1,sizeof(h));
    memset(d,0x3f,sizeof(d));
}

void add(int a,int b,int c)
{
    ne[idx]=h[a],e[idx]=b,h[a]=idx,w[idx++]=c;
}

int dijkstra()
{
    d[s]=0;
    for(int i=0 ; i<n ; i++)
    {
        int t=0;
        for(int j=1;j<=n;j++)
        {
            if(!st[j] && (!t || d[j]<d[t]))
                t=j;
        }
        st[t]=1;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]=min(d[j],d[t]+w[i]);
        }
    }
    if(d[n]==INF)return -1;
    return d[n];
}
int main()
{
    init();
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<d[i]<<' ';
    return 0;
}