#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}edge;
int a[10010],n,m,k,u,v,w,x,mn,sum;
bool f[10010];
vector<node> vc[10010];
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		a[i]=2147483647;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>edge.x>>edge.y;
		vc[u].push_back(edge);
		if(u==k)
			a[edge.x]=min(a[edge.x],edge.y);
	}
	a[k]=0;
	f[k]=1;
	for(int i=1;i<n;i++)
	{
		mn=2147483647;
		x=k;
		for(int j=1;j<=n;j++)
		{
			if(!f[j]&&mn>a[j])
			{
				
				mn=a[j];
				x=j;
			}
		}
		f[x]=1;
		for(int j=0;j<vc[x].size();j++)//这个循环RE
		{
			sum=vc[x][j].x;
			if(vc[sum][j].y<2147483647&&a[sum]>mn+vc[sum][j].y)
				a[sum]=mn+vc[sum][j].y;
		}
	}
	cout<<endl;
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
	/*
	4 6 1
	1 2 2
	2 3 2
	2 4 1
	1 3 5
	3 4 3
	1 4 4
	*/
}