#include <bits/stdc++.h>
using namespace std;
int n, m, S, cnt, ans[10000001], head[10000001];
struct Edge{
	int to,nxt,w;
}e[20000005];
void add_edge(int u,int v,int w){
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
struct node{
	int num,d;
	friend bool operator<(node a,node b){
		return a.d>b.d;
	}
};
priority_queue<node>q;
int main(){
	memset(ans,0x7f,sizeof(ans));
	memset(head,-1,sizeof(head));
	cin>>n>>m>>S;
	int u,v,w;
	for(int i = 1; i <= m; i++){
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	q.push(node{S,0});
	while(!q.empty()){
		node t = q.top();
		q.pop();
		if(ans[t.num]<t.d){
			continue;
		}
		ans[t.num] = t.d;
		for(int j = head[t.num];j!=-1;j = e[j].nxt){
			if(t.d+e[j].w<ans[e[j].to]){
				ans[e[j].to] = t.d+e[j].w;
				q.push(node{e[j].to,ans[e[j].to]});
			}
		}
	}
	for(int i = 1; i <= n; i++){
		cout << ans[i] << " ";
	}
	return 0;
}