#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
struct csq{
	int loc,num;
	friend bool operator <(csq a,csq b){a.num>b.num;};
};
struct node{int to,w;};
priority_queue<csq> q;
vector<node> e[100010];
int n,m,s,dis[100010],vis[100010]; 
void dijkstra(){
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[s]=0;
	q.push((csq){s,0});
	while(!q.empty()){
		int u=q.top().loc;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			node t=e[u][i];
			if(dis[t.to]>dis[u]+t.w){
				dis[t.to]=dis[u]+t.w;
				if(!vis[t.to])q.push((csq){t.to,dis[t.to]});
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back((node){v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}