RT

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s;
ll INF=2147483647;
const int N=1e4+2;
vector<pair<ll,ll>> G[N];
ll u,v,w;
ll minn,k;
ll dis[N];
bitset<N> bo;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		G[u].push_back(make_pair(v,w));	
	}
	for(int i=1;i<=n;i++){
		G[i].push_back(make_pair(i,0));
		dis[i]=INF;
	}
	dis[s]=0;
	for(int i=1;i<=n;i++){
		minn=INF*2;
		k=0;
		for(auto t:G[i]){
			v=t.first;
			w=t.second;
			if(dis[v]<minn && !bo[v]){
				minn=dis[v];
				k=v;
			}
		}	
		bo[k]=1;
		for(auto t:G[k]){
			v=t.first;
			w=t.second;
			dis[v]=min(dis[v],dis[k]+w);
		}
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	cout<<endl;
	return 0;
}