#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
const int maxm=5e5+10;
const int INF=1e7;
ll n,m,s,k,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge{
	ll tot,next,w;
}edge[maxm];
void add(ll u,ll v,ll w){
	edge[++k].next=head[u];
	edge[k].tot=v;
	edge[k].w=w;
	head[u]=k;
}
queue<ll> q;
void spfa(){
	for(ll i=1;i<=n;i++){
		dis[i]=INF;
	}
	ll u,v;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(ll i=head[u];i;i=edge[i].next){
			v=edge[i].tot;
			if(dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	
}
int main(){
	cin>>n>>m>>s;
	for(ll i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	} 
	spfa();
	for(ll i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	
	return 0;
}