#include<iostream>
#include<valarray>
using namespace std;
long long n , m , s , line[1001][1001] , dis[10001];
bool vist[10001]; 
int main()
{
	cin>>n>>m>>s;
	for(int i =1 ; i <= n ; i++)
	{
		for(int j = 1 ; j<= n ; j++)
		{
			if(i == j)line[i][j] = 0;
			else
			line[i][j] = 2147483647LL;
		}
	}
	int x1 , x2 , t;
	for(int i = 1 ; i<= m ; i++)
	{
		
		cin>>x1>>x2>>t;
		line[x1][x2] = t;
	}
	for(int i = 1 ; i<= n ; i++)	dis[i] = line[s][i];
	vist[s] = 1;
	int mt = s;
	long long mmin = 2147483647;
	int mm;
	for(int u = 1 ; u<= n ; u++)
	{
		mmin = 2147483647;
		mm = mt;
		for(int i = 1 ; i <= n ; i++)
		{
			if(mmin > line[mt][i] && vist[i] == 0)
			{
				mmin = line[mt][i];
			    mm = i;
			}
		}
		mt = mm;
		for(int i = 1 ; i<= n ; i++)
		{
		    if(vist[i] == 0 && line[mt][i] != 2147483647 && dis[i] > line[s][mt] + line[mt][i])
		    {
		    	dis[i] = dis[mt] + line[mt][i];
		    }
		}
		vist[mt] = 1;
	}
	for(int i = 1 ; i<= n ; i++)cout<<dis[i]<<" "; 
	return 0;
}