#include <bits/stdc++.h>
using namespace std;
int dp[100009];//起点到目标点的最短路径 
int n,m,p;
bool v[100009];
//int pre[100009];
struct ff{
	int weight,next,adj;
};
int g[1000009];
ff a[2000009];
int tot;
void add(int x,int y,int w){
	if(g[x]){
		int q;//顶点在邻接表的位置 
		for(int i=g[x];;i=a[i].next){
			q=i;
			if(a[i].next==0)break;
		}
		a[++tot].adj=y;
		a[q].next=tot;
		a[tot].weight=w; 
	}
	else {
		a[++tot].adj=y;
		g[x]=tot;
		a[tot].weight=w; 
	}	
}
int main()
{
	freopen("4779_1.in","r",stdin);
	freopen("4779.out","w",stdout);
	cin>>n>>m>>p;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		add(x,y,w);
	}
	
	for(int i=1;i<=n;i++)dp[i]=100000;
	dp[p]=0;
	for(int i=1;i<=n;i++){
		int k=100000,t=0;
		bool flag=0;
		for(int j=1;j<=n;j++){//
			if(!v[j]){
				if(k>dp[j]){
					k=dp[j];//dp[5]=0
					t=j;//t=5
					flag=1;
				}
			}
		}
		//cout<<t<<endl;
		v[t]=1;//v[5]=1
		for(int j=g[t];;j=a[j].next){//j=g[5]=6
			//cout<<i<<" "<<a[j].adj<<endl;
			if(!v[a[j].adj]){
				//cout<<dp[a[j].adj]<<"** "<<dp[t]<<" "<<a[t].adj<<" "<<a[j].weight<<endl;
				if(dp[a[j].adj]>dp[t]+a[j].weight){//t=5 dp[5]=0 +g[5]=6
					dp[a[j].adj]=dp[t]+a[j].weight;//
//					pre[a[j].adj]=t;
				}
			}
			
			//cout<<endl;
			if(a[j].next==0)break;
		}
		if(!flag)break;
	}
	//for(int i=1;i<=tot;i++)cout<<i<<" "<<a[i].adj<<" "<<a[i].weight<<endl;
	for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
	return 0;
}