#include<bits/stdc++.h>
using namespace std;
const int MaxN = 100010, MaxM = 500010;
int n,m,s,t,u,v,w,cnt,f[MaxN ],dis[MaxN ],vis[MaxN ];
struct Edge{
   int v,w,nxt;
}e[MaxM ];
void insert(int u,int v,int w){
   e[++cnt].v=v;
   e[cnt].w=w;
   e[cnt].nxt=f[u];
   f[u]=cnt; 
}
void dijkstra(int s){
   memset(dis,0x3f,sizeof dis);
   dis[s]=0;
   for(int i=1;i<=n;i++){
   	int minn=0x3f3f3f3f,u=-1;
   	for(int j=1;j<=n;j++){
   		if(dis[j]<minn&&vis[j]==0){
   			minn=dis[j];
   			u=j;
   		}	
   	}
   	if(u==-1) return ;
   	else vis[u]=1;
   	for(int j=f[u];j;j=e[j].nxt){
   		int v=e[j].v,w=e[j].w;
   		if(vis[v]==0&&dis[u]+w<dis[v]){
   			dis[v]=dis[u]+w;
   		}
   	}
   }	
}
int main(){
   cin>>n>>m>>s;
   for(int i=1;i<=m;i++){
   	cin>>u>>v>>w;
   	insert(u,v,w);
   }
   dijkstra(s);
   for(int i=1;i<=n;i++){
   	cout<<dis[i]<<" ";
   }
   return 0;
}