#include<bits/stdc++.h>
using namespace std;
int n,m,s,fron,num_edge,head[1000001],dis[1000001];
bool b[1000001];
struct Edge
{
  int next,to,dis;
}edge[1000001];
void add(int from,int to,int dis) 
{ 
	edge[++num_edge].next=head[from]; 
	edge[num_edge].to=to; 
	edge[num_edge].dis=dis; 
	head[from]=num_edge;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=n;i++) dis[i]=1e9;
	dis[s]=0;
	int cur=s;
	while(!b[cur])
	{
		long long minn=1e18;
		b[cur]=1;
		for(int i=head[cur];i;i=edge[i].next)
			if(!b[edge[i].to]&&dis[edge[i].to]>dis[cur]+edge[i].dis) dis[edge[i].to]=dis[cur]+edge[i].dis;
		for(int i=1;i<=n;i++)
			if(dis[i]<minn&&!b[i]) minn=dis[cur=i];
		
	}
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
}
/*5 15 5
2 2 270
1 4 89
2 1 3
5 5 261
5 2 163
5 5 275
4 5 108
4 4 231
3 4 213
3 3 119
3 1 77
3 1 6
2 4 83
5 5 196
5 5 94*/
//166 163 2147483647 246 0