#include<bits/stdc++.h>
#define M 100010
#include<queue> 
using namespace std;
struct node{
	int v,w,ne;
}e[M<<1]; 
int n,m,s,u,v,w,cnt;
int head[M],dis[M],vis[M];
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].ne=head[u];
	head[u]=cnt;
}
priority_queue<int,vector<int>,greater<int> > q;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++) cin>>u>>v>>w,add(u,v,w);
	q.push(s);  
	for(int i=1;i<=n;i++) dis[i]=0x3f3f3f;
	dis[s]=0;
	while(!q.empty()){
		int t=q.top();
		vis[t]=1;
		q.pop();              
		for(int i=head[t];i;i=e[i].ne){
			int j=e[i].v;
			if(dis[j]>dis[t]+e[i].w){
				dis[j]=dis[t]+e[i].w;
				if(vis[j]) continue;
				q.push(j);
			}
		}
		//for(int i=1;i<=n;i++) cout<<vis[i]<<' ';
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}