#include <iostream>
#include <vector>
using namespace std;


int kMax=0x7fffffff;

int getk(int *k, int m, int i, int j){
	for(int u=0; u<m; u++)
		if(k[u*3]==i && k[u*3+1]==j) return k[u*3+2];
	return kMax;
}





int main(){
//初始化变量 
	int lsbl; //lsbl临时变量； 
	int n,min,m;
	int w;
	int start;
	
// input
	cin>>n>>m>>start;
	
//初始化数组 
	vector<int> v[4];
	start--;
	int k[m][3];
	//int k1[n],k2[n];


	for(int i=0;i<m;i++){
		cin>>k[i][0]>>k[i][1]>>k[i][2];
		k[i][0]--;
		k[i][1]--;
	}
	for(int i=0;i<n;i++){
		v[0][i] = kMax;
		v[1][i] = kMax;
		v[2][i] = i;
		v[3][i] = 0;
	}
	v[0][0] = 0;
	v[3][0] = start;
	//k1[start] = 0;
	//k2[start] = kDone;
	for(int u=1;u<n;u++){
		// step 1 from k1 to k2
		for(int i=0;i<u;i++){
			for(int j=0;j<n-u;j++){
				int Kij=getk(&k[0][0], m, v[3][i],v[2][j]);
				if(Kij == kMax) continue;
				lsbl = v[0][i]+Kij;
//				cout<<"d("<<i<<","<<j<<")="<<lsbl<<" vs k2["<<j<<"]="<<k2[j]<<endl;
//				if(lsbl < k2[j] && k2[j] != kDone){
				if(lsbl < v[1][v[2][j]]){
					v[1][v[2][j]] = lsbl;
				}
			}
		}
		
		
		// step2 move min of k2 to k1
		min = 0;
//		for(int j=1;j<n;j++){
		for(int j=1;j<n-u;j++){
			if(v[1][v[2][j]] < v[1][v[2][min]]) min = j;
		}
		
		if(v[1][v[2][min]] == kMax) continue;
		v[0].push_back(v[1][v[2][min]]);
		v[1][v[2][min]] = v[1][v[1].size()-1];
		v[1].pop_back();
		v[3].push_back(v[2][min]);
		v[2][min] = v[2][v[2].size()-1];
		
	}
	
	// output
	for(int i=0;i<n-1;i++){
	    cout<<v[0][i]<<' ';
	}
	cout<<v[0][n-1];
}

/*
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

 
40000 2 1
1 2 1
1 4000 1
*/



//int kDone=0xffffffff-1;

//void log(int *d, int n){
//	for(int i=0;i<n;i++){
//		if(d[i] != kMax) cout<<d[i]<<" ";
//	}
//	cout<<endl;
//}