#include<bits/stdc++.h>
using namespace std;
int n,m,s,head[500005],cnt,to[500005],nex[500005],w[500005],dis[100005],vis[100005];
struct node{
	int pos,dis;
	bool operator < (const node &x) const{
		x.dis<dis;
	}
};
void add(int x,int y,int d)
{
	to[++cnt]=y;
	w[cnt]=d;
	nex[cnt]=head[x]; 
	head[x]=cnt;
}
priority_queue<node> a;
int main()
{
	 cin>>n>>m>>s;
	 for(int i=1;i<=n;i++)
	   dis[i]=INT_MAX;
	 for(int i=1;i<=m;i++)
	 {
	 	int x,y,d;
	 	cin>>x>>y>>d;
	 	add(x,y,d);
	 }
	 a.push( ( node ){s,0 } );
	 dis[s]=0;
	 while(!a.empty())
	 {
	 	int t,tt;
	 	node q=a.top();
	 	a.pop();
	 	t=q.pos;tt=q.dis;
		if(vis[t])
		  continue;
		vis[t]=1;
	 	for(int i=head[t];i;i=nex[i])
	 	{
	 		if(dis[to[i]]>w[i]+tt)
	 		{
	 			dis[to[i]]=w[i]+tt;
			    
	 		}
	 		 a.push((node){to[i],dis[to[i]]});
	 		
	 	}
	 }
	 for(int i=1;i<=n;i++)
	 {
	 	cout<<dis[i]<<" ";
	 }
}