#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 105
#define MAX_DIS 9999999999
int arrpath[MAX][MAX];
int n,m,s;
int dist[MAX];
bool visit[MAX];
void init(){
	for(int i=0;i<MAX;i++){
		for(int j=0;j<MAX;j++){
			arrpath[i][j]=MAX_DIS;
		}
		arrpath[i][i]=0;
	}
	memset(visit,false,sizeof(visit));
	for(int i=2;i<=n;i++){
		dist[i]=MAX_DIS;
	}
	dist[1]=0;
}
void create(){
	int v1,v2,weight;
	for(int i=1;i<=m;i++){
		cin>>v1>>v2>>weight;
		if(arrpath[v1][v2]>weight){
			arrpath[v1][v2]=weight;
			arrpath[v2][v1]=weight;
		}
	}
}
void dijstra(){
	while(1){
		int v=-1;
		for(int i=1;i<=n;i++){
			if(!visit[i]&&(v==-1||dist[i]<dist[v])){
				v=i;
			}
		}
		if(v==-1)break;
	visit[v]=true;
	for(int i=1;i<=n;i++){
		if(arrpath[v][i]){
			dist[i]=min(dist[i],dist[v]+arrpath[v][i]);
		}
	}
	}
}
int main(){
    cin>>n>>m>>s;
	if(!n&&!m){
		return 0;
	}else{
		init();
		create();
		dijstra();
}
for(int i=1;i<=n;i++){
cout<<dist[i]<<" ";
}
   return 0; 
}