#include<iostream>
#include<queue>
#include<vector>
using namespace std;
bool vis[10101];
int dis[10101];
struct node{
    int to,val;
    node(int to_,int val_):
    to(to_),val(val_){}
};
struct edge{
    int to,val;
    edge(int to_,int val_):
    to(to_),val(val_){}
    bool operator < (const edge &other) const
    {
        return val>other.val;
    }
};
vector<node>gra[10101];
priority_queue<edge>q;
void dijkstra(int s)
{
    q.push(edge(s,0));
    while(!q.empty())
    {
        edge temp=q.top();
        q.pop();
        if(vis[temp.to])continue;
        vis[temp.to]=1;
        for(int i=0;i<gra[temp.to].size();i++)
        {
            if(dis[temp.to]+temp.val<dis[gra[temp.to][i].to])
            {
                dis[gra[temp.to][i].to]=dis[temp.to]+temp.val;
                q.push(edge(gra[temp.to][i].to,dis[gra[temp.to][i].to]));
            }
        }
    }
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    for(int p=1,x,y,z;p<=m;p++)
    {
        cin>>x>>y>>z;
        gra[x].push_back(node(y,z));
    }
    dijkstra(s);
    for(int p=1;p<=n;p++)
        cout<<dis[p]<<endl;
    return 0;
}

求助啊，萌新刚学最短路QAQ