#include<bits/stdc++.h>
using namespace std;
vector <int> v[10010][5];
queue <int > q;
int dis[10010];
int book[10010];
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<m;i++){
		int u,v1,w;
		cin>>u>>v1>>w;
		v[u][1].push_back(v1);
		v[u][2].push_back(w);
	}
	for(int i=1;i<=n;i++){
		dis[i]=0x7fffffff;
	}
	dis[s]=0;
	q.push({s});
	book[s]=1;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		book[t]=0;
		for(int i=0;i<v[t][1].size();i++){
			int p=v[t][1][i];
			dis[p]=min(dis[p],dis[t]+v[t][2][i]);
			if(dis[p]==dis[t]+v[t][2][i]){
				if(!book[p]){
					book[p]=1;
					q.push({p});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
}