#include<bits/stdc++.h>
#define f(i,a,b) for(int i = a ; i<=b ; i++)
#define INF 99999999
using namespace std;
int n,m,s;
int u,v,w; 
int g[10005][10005],dis[10005],vis[10005] = {0};
void djstl(int s){
	dis[s] = 0;
	vis[s] = 1;	
	f(i,1,n) dis[i] = g[s][i];
	while(1){
		int pos = 0,minn = INF;
		f(j,1,n){
			if(!vis[j] && minn>dis[j]){
				pos = j;
				minn = dis[j];
			}
		}
		if(pos == 0) break;
		vis[pos] = 1;
		f(i,1,n) if(!vis[i] && dis[i]>dis[pos]+g[pos][i]) dis[i] = dis[pos]+g[pos][i];
	}
}
int main(){
	cin>>n>>m>>s;
	f(i,1,m){
		cin>>u>>v>>w;
		g[u][v] = w;
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	djstl(s);
	f(i,1,n){
		cout<<dis[i]<<" ";
	}
	return 0;
}

样例输出0 2 3 3 求调