#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9+10;
int n,m,s,dis[N],vis[N];//vis表示是否在队内 
vector<pair<int,int> > e[N];
queue<int> q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
	}
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0;vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop(); vis[u]=0;//出队后vis=0 
		for(auto p:e[u]){
			int v=p.first,w=p.second;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;//更新 
				if(!vis[v]) q.push(v),vis[v]=1;//不在队内，再入队 
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
	return 0;
}