#include<bits/stdc++.h>
using namespace std;
struct edge{
	int to,val;
	edge(int t,int w):to(t),val(w){}
};
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};
const int inf=1e9;
void solve(){//[1,index]模型 
	int n,m,s;cin>>n>>m>>s;//出发点 
	vector<int>dis(n+10,inf);
	vector<bool>vis(n+10,false);
	vector<list<edge>>grid(m+1);
	priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pq;
	
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		grid[u].push_back(edge(v,w));
	}
	dis[s]=0;
	pq.push(pair<int,int>(s,0));//存放出边和权重 
	
//	for(int i=1;i<=n;i++){
//		int minval=INT_MAX;
//		int cur=1;		
//		for(int v=1;v<=n;v++){
//			if(!vis[v]&&dis[v]<minval){
//				minval=dis[v];cur=v;
//			}
//		}
//		dis[cur]=true;
//		
//		for(int v=1;v<=n;v++){
//			if(!vis[v]&&grid[cur].first!=inf&&dis[cur]+grid[].second<dis[v]){
//				
//			}//如果这个点没有被访问，如果这个点联通着cur，dis[cur]+grid[cur][]<dis[v] 
//		}
//		pair<int,int>cur=pq.top();pq.pop();
//		vis[cur.first]=true;
//		
//		for(pair<int,int>i:grid[cur.first]){
//			if(!vis[i.frist]&&dis[cur.first]+i.second<dis[i.first]){
//				dis[i.first]=dis[cur.first]+i.second;
//				pq.push(pair<int,int>(i.first,dis[i.first]));
//			}
//		}
//	}
	while(!pq.empty()){
		pair<int,int>cur=pq.top();pq.pop();
		if(vis[cur.first]) continue;
		
		vis[cur.first]=true;
		
		for(edge i:grid[cur.first]){
			if(!vis[i.to]&&dis[cur.first]+i.val<dis[i.to]){
				dis[i.to]=dis[cur.first]+i.val;
				pq.push(pair<int,int>(i.to,dis[i.to]));
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		if(dis[i]==inf) cout<<INT_MAX<<" ";
		else cout<<dis[i]<<" ";
	} 	
}
int main(){
	int t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

WA了一个点，求条