#include<bits/stdc++.h>
#define INF 0x3f3f3f
using namespace std;
const int N=1e4+5;
int dis[N],a[N][N],st[N];
int n,m,s,x,y,w;
void dijkstra(int u){
	int mn,mns=INF;
	dis[u]=0;
	while(1){
		mn=0,mns=INF;
		for(int i=1;i<=n;i++){
			if(!st[i]&&mns>dis[i]){
				mns=dis[i];
				mn=i;
			}
		}
		if(mn==0)break;
		st[mn]=1;
		for(int i=1;i<=n;i++){
			if(dis[i]>dis[mn]+a[mn][i]){
				dis[i]=dis[mn]+a[mn][i];
			}
		}
	}
}
int main(){
	memset(a,INF,sizeof a);
	memset(st,0,sizeof st);
	memset(dis,INF,sizeof dis);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)a[i][i]=0;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>w;
		a[x][y]=min(a[x][y],w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		if(dis[i]==INF) cout<<pow(2,31)-1<<' ';
		else cout<<dis[i]<<' ';
	}
	return 0;
}