#include<bits/stdc++.h>
using namespace std;
int a[2001][2001];
int main()
{
	int i,j,k,n,m,x,y,z,s;
	cin>>n>>m>>s;
	for(i=1;i<=n;i=i+1)
	{
		for(j=1;j<=n;j=j+1)
		{
			a[i][j]=99999999;
		}
	}
	for(i=1;i<=m;i=i+1)
	{
		cin>>x>>y>>z;
		a[x][y]=z;
	}
	for(k=1;k<=n;k=k+1)
	{
		for(i=1;i<=n;i=i+1)
		{
			for(j=1;j<=n;j=j+1)
			{
				if(a[i][j]>a[i][k]+a[k][j])
				{
					a[i][j]=a[i][k]+a[k][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(a[s][i]==99999999)
		cout<<"0"<<" ";
		else
		cout<<a[s][i]<<" ";
	}
	return 0;
}