#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define Max 2147483647
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
struct node{
	int start;
	int end;
	int value;
};
node edge[500005];
int head[500005],next[500005];
int dist[10005],v[10005];
int N,M,K;
queue<int> x;
void SPFA(){
	memset(v,0,sizeof(v));
	for(int i=1;i<=N;i++){
		dist[i]=Max;
	}
	dist[K]=0;
	x.push(K);
	v[K]=1;
	while(x.size()!=0){
		int y=x.front();
		x.pop();
		for(int i=head[y];i;i=next[i]){
			int end=edge[i].end,value=edge[i].value;
			if(dist[end]>dist[y]+value){
				dist[end]=dist[y]+value;
				if(v[end]==0){
					x.push(end);
					v[end]=1;
				}
			}
		}
	}
}
int main(){
	N=read();
	M=read();
	K=read();
	for(int i=1;i<=M;i++){
		edge[i].start=read();
		edge[i].end=read();
		edge[i].value=read();
		next[i]=head[edge[i].start];
		head[edge[i].start]=i;
	}
	SPFA();
	for(int i=1;i<=N;i++){
		printf("%d ",dist[i]);
	}
	return 0;
}