#include<bits/stdc++.h>
using namespace std;
const long long inf=2147483647;
int n,m,k,sy; 
struct edge{
	int from;
	int to;
	int next;
	int len;
}a[200002];
struct node{
	int u,v,w;
}e[200002];
bool cmp(node x,node y){
	if(x.u==y.u and x.v==y.v) return x.w<y.w;
	else if(x.u==y.u) return x.v<y.v;
	else return x.u<y.u;
}
 
int pre[200002];
int s=1,t;
int f[200002];//判定是否查找 
long long dis[200002];//从1到下标点的最短路径 
void add(int u,int v,int l){
	k++;
	a[k].from=u;
	a[k].to=v;
	a[k].len=l;
	a[k].next=pre[u];
	pre[u]=k;
}
queue<int> q;
void spfa(){
	for(int i=1;i<=n;i++){
		dis[i]=pow(2,31)-1;
		f[i]=false;
	}
	dis[sy]=0;//自己到自己为0 
	q.push(sy);//自己入队 
	f[sy]=true;//自己已经走过 
	while(!q.empty()){
		int h=q.front();//获取头元素 
		q.pop();//走前出队 
		f[h]=false; //标记未走，已出队,方便再次判断最短路径
		for(int i=pre[h];i!=0;i=a[i].next){//查找h能去的所以点 
			int to=a[i].to;//当前这个h能去的点能走到的点 
			if(dis[to]>dis[h]+a[i].len){//旧路径只比新路径值（到h路径+h能去点的路径）长 
				dis[to]=dis[h]+a[i].len;//将新路径放入路径数组中 
				if(!f[to]){//未查找 
					q.push(to);//查找到新的最短路径,to入队 
					f[to]=true;//标记查找 
				}
			}
		}	
		
	}
}
int main(){
	cin>>n>>m>>sy;
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
//		int f,g,w;
//		cin>>f>>g>>w;
//		add(f,g,w);
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(u==e[i-1].u and v==e[i-1].v) continue;
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++){
		if(i==sy) cout<<0<<" ";
		else cout<<dis[i]<<" ";
	}
}