#include <bits/stdc++.h> 
using namespace std;
int a[10010][10010],d[50010],n,m,s;
bool v[10010];

void dijkstra()
{
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	d[s]=0;
	for(int i=s;i<n;i++)
	{
		int x=0;
		for(int j=s;j<=n;j++)
		{
			if(!v[j] && (x==0 || d[j]<d[x])) x=j;
		}
		v[x]=1;
		for(int y=s;y<=n;y++)
			d[y]=min(d[y],d[x]+a[x][y]);
	}
}
int main()
{
	cin >> n >> m >> s;
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++) a[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		a[x][y]=min(a[x][y],z);
	}
	dijkstra();
	for(int i=s;i<=n;i++)
		cout << d[i] << " ";
	cout << endl;
	return 0;
}