#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,inf=1000000010;
int n,m,cnt,dis[maxn],head[maxn],to[2*maxn],ne[2*maxn],edge[2*maxn],start,d;
bool vis[maxn];
void dijkstra(){
	for(int i=1;i<=n;i++){
		int k,minn=inf;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]<minn){
				k=j;minn=dis[j];
			}
		}
		vis[k]=1;
		for(int j=head[k];j!=0;j=ne[j]){
			int v=to[j];
			if(dis[k]+edge[j]<dis[v]){
				dis[v]=dis[k]+edge[j];	
			}
		}
	}
	return;
}
int main(){
	memset(dis,127,sizeof(dis));
	scanf("%d%d%d",&n,&m,&start);dis[start]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		edge[++cnt]=w;to[cnt]=v;ne[cnt]=head[u];head[u]=cnt;
	}   
	dijkstra(); 
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}