#include<bits/stdc++.h>
using namespace std;
short lin[10001][10001];
int biao[10001];
int duan[10001];
int main() {
	int n,m,s,qi;
	cin>>n>>m>>s;
	qi=s;
	memset(lin,0x3f3f3f,sizeof(lin));
	for(int i=1; i<=m; i++) {
		short a,b,c;
		cin>>a>>b>>c;
		lin[a][b]=min(lin[a][b],c);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(lin[i][j]==0x3f3f3f){
				lin[i][j]=0;
			}
		}
	} 
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<lin[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	int minn=0x3f3f3f;
	duan[s]=0;
	for(int l=2; l<=n; l++) {
//		cout<<l<<endl<<endl;
		memset(biao,0,sizeof(biao));
		biao[qi]=1;
//		memset(duan,0,sizeof(duan));
		s=qi;
		for(int i=2; i<=l; i++) {
			minn=0x3f3f3f;
			int qu=0;
//			int minnn=0x3f3f3f3f;
			for(int j=1; j<=l; j++) {
				if(lin[s][j]!=0&&lin[s][j]+duan[s]<minn&&j!=s&&!biao[j]) {
					minn=lin[s][j]+duan[s];
//					cout<<s<<" "<<j<<endl;
					qu=j;
				}
			}
			s=qu;
			biao[qu]=1;
			if(duan[qu]==0){
				duan[qu]=minn;
			}
//			cout<<qu<<" ";
		}
//		for(int i=1;i<=n;i++){
//			cout<<duan[i]<<" ";
//		}
//		cout<<endl;
//		cout<<minn<<" ";
	}
	for(int i=1; i<=n; i++) {
		cout<<duan[i]<<" ";
	}
	return 0;
}

求求了