#include<bits/stdc++.h>
using namespace std;
int n,m,s,ans[10010],a[10010][10010];
bool visit[10010];
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		ans[i]=2147483647;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z;
		if(x==s)
		{
			ans[y]=z;
		}
	}
	visit[s]=1;
	ans[s]=0;
	for(int i=1;i<=n;i++)
	{
		int mid,min1=2147483647;
		for(int u=1;u<=n;u++)
		{
			if(min1>ans[u]&&visit[u]==0)
			{
				min1=ans[u];
				mid=u;
			}
		}
		visit[mid]=1;
		for(int u=1;u<=n;u++)
		{
			if(visit[u]==0&&ans[u]>ans[mid]+a[mid][u])
			{
				ans[u]=ans[mid]+a[mid][u];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<" ";
	}
	return 0;
 }