#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> p;
int n,m,s,u,v,a;
int min_dis[500010],mark[500010];
vector<pair<int,int>> g[500010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>a;
		g[u].push_back({v,a});
	}
	for(int i=1;i<=n;i++) min_dis[i]=INT_MAX;
	min_dis[s]=0,p.push({s,0});
	while(!p.empty()){
		int to=p.top().first,dis=p.top().second;
		p.pop();
		if(mark[to]==1) continue;
		mark[to]=1;
		for(auto e:g[to]){
			int tmp=e.second+dis;
			if(tmp<min_dis[e.first]){
				min_dis[e.first]=tmp;
				if(!mark[e.first]){
					p.push({e.first,tmp});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<min_dis[i]<<' ';
	}
	return 0;
}