RT

#include<bits/stdc++.h>
using namespace std;
#define I(e) for(int i=1;i<=e;i++)
#define J(e) for(int j=1;j<=e;j++)
const int NUL = 0x3f;
//Floyd or SPFA
//~= dfs
struct node{
	int to;
	int l;
	node(int v,int w){
		to=v;
		l=w;
	}
};
queue<int>q;
vector<node>e[10010];
int dp[10010];
int n,m,s;
bitset<10010>v;
void SPFA(int st){
	dp[st]=0;
	q.push(st);
//	cout<<"K";
	while(q.size()){
//		cout<<"L";
		s=q.front();
		v[st]=0;
		q.pop();
		for(int i=0;i<e[s].size();i++){
//			cout<<"s="<<s<<",i="<<i<<",dp[s]+e[s][i]="<<dp[s]+e[s][i]<<endl;
			if(dp[e[s][i].to]>dp[s]+e[s][i].l&&v[i]==0){
				dp[e[s][i].to]=dp[s]+e[s][i].l;
//				cout<<":"<<dp[i];
				q.push(i);
				v[i]=1;
			}
		}
	} 
}
int main(){
	cin>>n>>m>>s;
	memset(dp,NUL,sizeof(dp));
	memset(e,NUL,sizeof(e));
	I(m){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
//		node a;
//		a.to=y;
//		a.l=z;
//		e[x][y]=z;
//		cout<<1<<endl;
	e[u].push_back(node(v,w));
//		cout<<u<<" "<<v<<" "<<w<<endl;
	}
	SPFA(s);
//	cout<<endl;
	I(n){
		if(dp[i]>=NUL)
			printf("2147483647 ");
		else
			printf("%d ",dp[i]);
	}
	return 0;
}