#include<fstream>
using namespace std;
#define infinit 1000000000
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int c[1200][1200],n,m,t[1200],s[1200],d[1200];

void citire(){
	in>>n>>m;
	int x,y,ct;
	for(int i=1;i<=n;i++){
		in>>x>>y>>ct;
		c[x][y]=ct;
	}
}
void dijkstra(int r){
	for(int i=1;i<=n;i++){
		d[j]=c[r][i];
		if(d[j]==0&&i!=r)
			s[i]=infinit;
		if(d[i]<infinit) t[i]=r;
	}
	t[r]=0;
	s[r]=1;
	for(int j=1;j<=n;j++)
		int min=infinit,poz;
	for(int i=1;i<=n;i++)
		if(!s[i])
			if(d[i]<min){
				poz=i;
				min=d[i];
			}
			s[poz]=1;
			for(int i=1;i<=n;i++)
				if(!s[i]){
					int sc=d[poz]+c[poz][i];
					if(sc<d[i]){
						d[i]=sc;
						t[i]=poz;
					}
				}
}
void main(){
	citire();
	int r;
	in>>r;
	dijkstra();
	for(int i=1;i<=n;i++)
		out<<d[i]<<" ";
	out<<endl;
	return 0;
}