#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int edges;
struct Edge{
	int next;
	int weight;
	int to;
}edge[500005];
int head[10005];
int dis[10005],vis[10005];
void add_Edge(int u,int v,int w)
{
	edges++;
	edge[edges].to=v;
	edge[edges].weight=w;
	edge[edges].next=head[u];
	head[u]=edges;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add_Edge(u,v,w);
	}
	for(int i=1;i<=n;i++)
		dis[i]=0x7fffffff;
	dis[s]=0;
	int pos=s;
	while(!vis[pos])
	{
		long long minn=0x7fffffff;
		vis[pos]=1;
		for(int i=head[pos];i;i=edge[i].next)
			if(!vis[edge[i].to]&&dis[edge[i].to]>dis[pos]+edge[i].weight)
				dis[edge[i].to]=dis[pos]+edge[i].weight;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dis[i]<minn)
				minn=dis[i],pos=i;
	}
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	return 0;
}