#include<bits/stdc++.h>
using namespace std;
const int M=200010,N=100010,inf=1234567890;
int n,m,s,head[N],cnt=1,dis[N];
bool vis[N];
long long ans;
priority_queue < pair <int,int>,vector <pair <int,int>>,greater <pair <int,int> > > q;

struct aa{
    int u,v,w,next;
}f[M];
void adde(int u,int v,int w){
    f[cnt].u=u;
    f[cnt].v=v;
    f[cnt].w=w;
    f[cnt].next=head[u];
    head[u]=cnt++;
}
void dijkstra(int s){
    memset(dis,inf,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(int i=head[u];i!=-1;i=f[i].next){
          int ev=f[i].v,ew=f[i].w;
          if(dis[ev]>dis[u]+ew) {
              dis[ev]=dis[u]+ew;
              q.push(make_pair(dis[ev],ev));
          }
        }
    }
    return ;
}
int main(){
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adde(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}