#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int u,v,w;
long long ans[100001];
queue<int>myque;
struct node
{
    int data;
    node *next;
    int wt;
    bool judge;
}f[100001];

void dijkstra()
{
    while(!myque.empty())
    {
        node *p=new node;
        p=&f[s];
        while(p->next!=NULL&&f[s].judge==false)
        {
            ans[p->next->data]=min(ans[p->next->data],ans[f[s].data]+p->next->wt);
            myque.push(p->next->data);
            p=p->next;
        }
        f[s].judge=true;
        myque.pop();
        s=myque.front();
    }
}

int main()
{
    cin>>n>>m>>s;
    int tem=s;
    memset(ans,63,sizeof(ans));
    ans[s]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        node *p=new node;
        p->data=v;
        p->wt=w;
        p->next=f[u].next;
        f[u].next=p;
    }

    for(int i=1;i<=n;i++)
        f[i].data=i;
    myque.push(s);
    dijkstra();
    for(int i=1;i<=n;i++)
    {
            cout<<ans[i]<<" ";
    }
    system("pause");
    return 0;
}