#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
typedef pair<int,int> PII; 
int dist[N];
bool st[N];
int h[N],w[N],e[N],ne[N],idx;
int n,m,s;
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(){
	priority_queue<PII,vector<PII>,greater<PII> > heap; 
	memset(dist,0x3f,sizeof dist);
	dist[s]=0ll;
	heap.push({0ll,s});
	while(heap.size()){
		PII t=heap.top();
		heap.pop();
		int ver=t.second,dis=t.first;
		if(st[ver]) continue;
		for(int i=h[ver];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dis+w[i]){
				dist[j]=dis+w[i];
				if(!st[j]){
					heap.push({dist[j],j});
				}
			}
		}
	}
}
signed main()
{
	memset(h,-1,sizeof h);
	scanf("%lld%lld%lld",&n,&m,&s);
	while(m--){
		int u,v,w;
		scanf("%lld %lld %lld",&u,&v,&w);
		add(u,v,w);
	}
//	floyd();
	dijkstra();
//	spfa(); 
//	printf("%d\n",dist[n]);
	for(int i=1;i<=n;i++) printf("%lld ",dist[i]);
	return 0;
}