#include<iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue <pair<int,int> >q;
vector <int>d,dis,to,nxt,head;
vector <bool>vis;
const int inf = 1e9 + 1;
int n,m,s;
void my_add(int u,int v,int w){
	dis.push_back(w);
	to.push_back(v);
	nxt.push_back(head[u]);
	head[u] = nxt.size() - 1;
	return;
}
void dijkstra(){
	d[s] = 0;
	q.push(make_pair(0,s));
	while(q.size()){
		int x = q.top().second;q.pop();
		if(vis[x] == true)continue;
		for(int i = head[x]; i != -1; i = nxt[i]){
			int y = to[i];
			int z = dis[i];
			if(d[y] > d[x] + z){
				d[y] = d[x] + z;
				q.push(make_pair(-d[y],y));
			}
		}
		
	}
	return;
}
int main(){
	cin>>n>>m>>s;
	head.resize(n+1,-1);
	d.resize(n+1,inf);
	vis.resize(n+1,false);
	
	for(int i = 1; i <= m; ++i){
		int u,v,w;
		cin>>u>>v>>w;
		my_add(u,v,w);
	}
	
	
	dijkstra();
	
	for(int i = 1; i <= n; ++i){
		if(d[i] == inf){
			cout<<2147483647<<' ';
		}else{
			cout<<d[i]<<' ';
		}
	}
	return 0;
} 

题目：P4779