#include<bits/stdc++.h>
#define int long long
#define mat(a,b) memset(a,b,sizeof(a)) 
#define MAX_V 10005
#define MAX_E 500005
#define inf 0x3f
using namespace std;
struct edge {
	int from ;
	int to ;
	int cost ;
};
edge es[MAX_E];
int d[MAX_V];
int v,e,s;
void bellman_ford(int s){
	mat(d,inf);
	d[s]=0;
	while(1){
		bool update=false;
		for(int i=1;i<=e;i++){
			edge e=es[i];
			if(d[e.from]!=inf && d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				update=true;
			}
		}
		if(!update) break;
	} 
}
signed main(){
	cin>>v>>e>>s;
	for(int i=1;i<=e;i++){
		cin>>es[i].from>>es[i].to>>es[i].cost;
	}
	bellman_ford(s);
	for(int i=1;i<=v;i++){
		if(d[i]!=0x3f3f3f3f) cout<<d[i]<<" ";
		else cout<<pow(2,31)-1<<" ";
	}
	return 0;
}

bellman-ford算法，60pts,WA*4