#include<iostream.h>
#include<fstream.h>
#define INF 32000
int n,m,i,d[100],e1,e2,c,x,a[100][100],k,nr[100],t,pc;
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>e1>>e2>>c;
		a[e1][e2]=c;
	}
	f>>x;
	k=0;
	for(i=1;i<=n;i++)
	{
		d[i]=INF;
		if(a[x][i]<INF && a[x][i]) d[i]=a[x][i];
		k++;
		nr[k]=i;
	}
	t=n;
	pc=1;
	
	while(t)
	{
		
	for(i=1;i<=n;i++)
		if(a[nr[pc]][i])
		{
			k++;
			if(a[nr[pc]][i]+d[nr[pc]]<d[i]) d[i]=a[nr[pc]][i]+d[nr[pc]];
			nr[k]=i;
		}
		pc++;
		t--;
	}
	for(i=1;i<=n;i++) if(d[i]!=INF) g<<d[i]<<" ";
}