#include<bits/stdc++.h>
using namespace std;
int dis[1005];
int n,m,s;
const int Max=2147483647;
struct road{
	int r[1001],len[1001];
	int tail;
}road[1001];
bool blue[1001];
int ds;
void run(int st){
	blue[st]=1;
	for(int i=1;i<=road[st].tail;i++){
		dis[road[st].r[i]]=min(dis[road[st].r[i]],dis[st]+road[st].len[i]);
		ds++;
		/*for(int jj=1;jj<=n;jj++){
			cout<<dis[jj]<<' ';
		}
		cout<<endl;*/
		run(road[st].r[i]);
	}
	return;
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		dis[i]=Max;
		bool flag=0;
		for(int j=1;j<=road[x].tail;j++){
			if(road[x].r[j]==y){
				road[x].len[j]==min(road[x].len[j],z);
				flag=1;
				break;
			}
		}
		if(!flag){
			road[x].r[++road[x].tail]=y;
			road[x].len[road[x].tail]=z;
		}
		
	}
	dis[s]=0;
	run(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}

打dijkstra的时候弄出来的，单源最短路可负权，姑且叫做disloyd。。。