//spfa
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#define INF 2147483647
using namespace std;
struct node{
	int to,next,w;
}t[1000001];
int head[500005],js,vis[500005];
long long dis[500005]; 
inline void add(int u,int v,int w){
	t[++js].next=head[u];
	t[js].to=v; t[js].w=w;
	head[u]=js;
}
queue<int>q;
int n,m,s;
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	} 
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0; q.push(s); vis[s]=1;
	while(q.size()!=0){
		int x=q.front(); q.pop(); vis[x]=0;
		for(int i=head[x];i;i=t[i].next){
			if(dis[t[i].to]>dis[x]+t[i].w){
				dis[t[i].to]=dis[x]+t[i].w;
				if(vis[t[i].to]!=1){
					q.push(t[i].to); vis[i]=1;
				}
			}
		}
	} 
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
 }