输入：5 15 5 2 5 181 1 5 98 4 2 49 3 2 262 4 3 26 2 4 192 5 1 221 2 2 254 4 4 233 1 5 44 5 4 67 4 2 214 1 1 47 1 1 118 5 4 3

输出：0 0 0 0 0

code：

/*
测试输入：
5 15 5 
2 5 181 
1 5 98 
4 2 49 
3 2 262 
4 3 26 
2 4 192 
5 1 221 
2 2 254 
4 4 233 
1 5 44 
5 4 67 
4 2 214 
1 1 47 
1 1 118 
5 4 3
测试输出：
221 52 29 3 0
*/
#include <bits/stdc++.h>
#define M 2147483647 //如果无法达到就输出M
using namespace std;
int n,m,s,u,v,w,g[10005][10005],dis[10005],vis[10005],temp=2e8,pos;
int main(){
	memset(g,1e8,sizeof(g));
	scanf("%d%d%d",&n,&m,&s);//输入点、边、起点
	for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);g[u][v]=min(g[u][v],w);}
	vis[s]=1,dis[s]=0;
	for(int i=1;i<=n;i++)g[i][i]=0,dis[i]=g[s][i];//初始化
	for(int i=1;i<n;i++){//dij
		temp=1e8;
		for(int j=1;j<=n;j++)
			if(g[s][j]<temp&&vis[j]==0)
				temp=g[s][j],pos=j;
		vis[pos]=1;
		for(int j=1;j<=n;j++)
			if(vis[j]==0&&g[pos][j]!=1e8)
				if(temp+g[pos][j]<dis[j])dis[j]=temp+g[pos][j];
	}
	for(int i=1;i<=n;i++){
		if(dis[i]!=1e8)cout<<dis[i]<<' ';
		else cout<<M<<' ';
	}
	return 0;
}