#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct b{int u,v,w;};
vector<b>a;
int ans[10005];
void bellman_ford()
{
	for(int i=1;i<=n;i++) ans[i]=(1<<31)-1;
	ans[s]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<m;j++)
			if(ans[a[j].v]>ans[a[j].u]+a[j].w)
				ans[a[j].v]=ans[a[j].u]+a[j].w;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a.push_back({u,v,w});
	}
	bellman_ford();
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}