#include <bits/stdc++.h>
using namespace std;
struct Edge
{
  int to;
  int next;
  int w;
} edge[1000000];
int n,m,s,w,v,u;
int p[1000000],edge_num,vis[1000000],dist[1000000];
void add_edge(int x,int y,int v)
{
	edge[++edge_num].next=p[x];
	edge[edge_num].to=y;
	edge[edge_num].w=v;
	p[x]=edge_num;
}
void spfa()
{
	int i,j,x,tmp;
	queue<int>que;
	for(i=1;i<=n;i++)
	dist[i]=INT_MAX;
	dist[s]=0;
	vis[s]=1;
	que.push(1);
	while(!que.empty())
	{
	   x=que.front();
       que.pop();
       vis[x]=0;
       for(i=p[x];i;i=edge[i].next)
       {
       	tmp=edge[i].to;
       	if(dist[tmp]>dist[x]+edge[i].w)
       	dist[tmp]=dist[x]+edge[i].w;
       	if(!vis[tmp])
       	{
       		vis[tmp]=1;
       		que.push(tmp);
		}
	   }
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++)
	cout<<dist[i]<<" "; 
	return 0;
}