rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
const int inf=1e18;
int n,m,i,u,v,w,s,dis[N];
bool vis[N];
vector<int> e[N];
vector<int> val[N];
queue<int> q;
void add(int u,int v,int w)
{
	e[u].push_back(v);
	val[u].push_back(w);
}
void init()
{
	for(i=1;i<=n;i++) dis[i]=inf;
	dis[s]=0;
	q.push(s);
}
void spfa()
{
	init();
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		vis[u]=1;
		for(i=0;i<e[u].size();i++)
		{
			v=e[u][i],w=val[u][i];
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
signed main()
{
	cin>>n>>m>>s;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
	}
	spfa();
	for(i=1;i<=n;i++)
	{
		if(dis[i]>=inf) dis[i]=(long long)(1<<31)-1;
		cout<<dis[i]<<' ';
	}
	return 0;
}