#include<fstream>
#include<iostream.h>
#define inf 1<<20
#define NMAX 10000
using namespace std;
int c[NMAX][NMAX];
int d[NMAX];
int n,k,m[NMAX],pred[NMAX],x0;
void afis();
void citire()
{
	ifstream f("dijkstra.in");
	f>>n>>k>>x0;
	int i,j,x,y,cost;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j) c[i][j]=c[j][i]=inf;
	for(i=1;i<=k;i++)
		{
			f>>x>>y>>cost;
			c[x][y]=c[y][x]=cost;
		}
	for(i=1;i<=n;i++)
	{
		d[i]=c[x0][i];pred[i]=x0;
	}
	m[x0]=1;pred[x0]=0;
	f.close();
}
void dijkstra ()
{
	int i,j,poz;
	for(i=1;i<=n;i++)
	{
		int minim=inf;
		for(j=1;j<=n;j++)
			if(!m[j] && minim>d[j]) {minim=d[j];poz=j;}
		m[poz]=1;
		for(j=1;j<=n;j++)
			while(!m[j] && d[j]>d[poz]+c[poz][j])
			{
				d[j]=d[poz]+c[poz][j];
				
				pred[j]=poz;
			}
	}
}
void afis()
{
	int i,j,drum[NMAX];
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		fout<<d[i]<<' ';
	fout.close();
}
int main ()
{
	citire();
	dijkstra();
	afis();
	return 0;
}