#include<bits/stdc++.h>
#define ll long long
#define inf 2147483647
using namespace std;

ll n, m, s, u, v, w;
struct point{
	ll to, next, w;
};
point arr[50010];
ll head[50010];
ll dis[50010];
bool markk[50010];
void dejsktra(){
	for(int i=0; i<50010; i++)
		dis[i]=inf;
	dis[s]=0;
	for(int k=1; k<=n; k++){
		int t=-1;
		for(int i=1; i<=n; i++){
			if(!markk[i]&&(t==-1||dis[i]<dis[t])){
				t=i;
			}
		}
		markk[t]=true;//t为最小值 
		for(int k=head[t]; k!=-1; k=arr[k].next)
			dis[arr[k].to]=min(dis[arr[k].to], dis[t]+arr[k].w);
	}
}

int main(){
	scanf("%lld %lld %lld", &n, &m, &s);
	for(int i=0; i<50010; i++)
		head[i]=-1;
	for(int i=1; i<=m; i++){
		scanf("%lld %lld %lld", &u, &v, &w);
		arr[i].to=v, arr[i].w=w, arr[i].next=head[u];
		head[u]=i;
	}
	dejsktra();
	for(int i=1; i<=n; i++){
		printf("%lld ", dis[i]);
	}
	return 0;
}