#include <bits/stdc++.h>
using namespace std;
const long long MAXN=1000000+10;
const long long inf=LONG_LONG_MAX;
long long n,m,s;
struct Node{
   long long  v,w;
   Node(long long _v,long long _w){
   	 v=_v;w=_w;
   }
};
vector<Node> G[MAXN];  
struct HeapNode{
   long long v;
   long long dist;   
   HeapNode(long long _v,long long _dist){
   	 v=_v;dist=_dist;
   }
};

struct cmp{
	bool operator()(HeapNode a,HeapNode b){
		return a.dist>b.dist;
	}
};
priority_queue<HeapNode,vector<HeapNode>,cmp> q;

bool vis[MAXN];
long long d[MAXN];
void dijkstra(long long s){	
	memset(vis,false,sizeof(vis));	
	for(long long i=1;i<=n;i++) d[i]=inf;  	
	d[s]=0;
	q.push(HeapNode(s,0));	
	while(q.size()){		
		long long x=q.top().v;q.pop();
		vis[x]=true;
		for(long long i=0;i<G[x].size();i++)
		{	
			long long y=G[x][i].v;
			long long z=G[x][i].w;
			if(!vis[y]&&d[x]+z<d[y]) {
				d[y]=d[x]+z; 
				q.push(HeapNode(y,d[y]));
				
		    }
		} 
  	}	 
}

int main()
{
	cin>>n>>m>>s;
    for(long long i=1;i<=m;i++){
		long long  u,v,w;
		cin>>u>>v>>w;
    	G[u].push_back(Node(v,w));
	}

	dijkstra(s);
		
	for(long long i=1;i<=n;i++)
		cout<<d[i]<<" ";
	return 0;
}