#include<bits/stdc++.h>
using namespace std;
int n,m,s,dis[100100],u,v,d,p[100100]; 
int next[200010],head[100100],cnt;
struct N1{
	int u,v,d;
}w[200010];
void add(int u,int v,int d)
{
	w[++cnt].u=u;
	w[cnt].v=v;
	w[cnt].d=d;
	next[cnt]=head[u];
	head[u]=cnt;
} 
struct node{
	int d,id;
};
node l;
struct cmp{
bool operator()(const node&a,const node&b)
{
	return a.d>b.d; 
}
};
priority_queue<node, vector<node>,cmp>q;
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&d);
		add(u,v,d);
	}
	q.push((node){0,s});
	for(int i=1;i<=n;i++)
	dis[i]=0x3fffffff;
	dis[s]=0;
    while(!q.empty())
	{
	 node k=q.top();
	 q.pop();
	 if(p[k.id])continue;
	 p[k.id]==1;
	 for(int i=head[k.id];i;i=next[i])
	 if(dis[w[i].v]>w[i].d+dis[w[i].u])
	 {
	 dis[w[i].v]=w[i].d+dis[w[i].u];
   if(!p[w[i].v])q.push((node){dis[w[i].v],w[i].v});
	 }
	}
	for(int i=1;i<=n;i++)
	printf("%d ",dis[i]);
	return 0;
}