#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s,mp[10005][10005],dis[10005],vis[10005];

void dijkstra(int s)//堆优化版本 
{
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int>,vector<int,int>,greater<pair<int,int> > > q;//堆优化关键
	q.push(make_pair(0,s));
	dis[s]=0;
	while(!q.empty())
	{
		pair<int,int> t=q.top();
		q.pop();
		if(vis[t.second])continue;
		vis[t.second]=1;
		for(int i=1;i<=n;i++)
		{
			if(dis[i]>dis[t.second]+mp[t.second][i])
			{
				dis[i]=dis[t.second]+mp[t.second][i];
				q.push(make_pair(dis[i],i));
			}
		}		
	} 
}
int main()
{
	cin>>n>>m>>s;
	memset(mp,INF,sizeof(mp));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		if(mp[u][v]>w)mp[u][v]=w;
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}