#include<bits/stdc++.h>
using namespace std;
int h[100005];
pair<int,int>heap[100005];
int dis[100005];
int pos[100005];
bool vis[100005];
int tot_edge,tot;
template<typename T> inline T read() {
  T X = 0; bool flag = 1; char ch = getchar();
  while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
  while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
  if (flag) return X;
  return ~ (X - 1);
}
inline void up(int x){
	while(heap[x].first<heap[x>>1].first&& (x>>1)>0){
		swap(heap[x],heap[x>>1]);
		swap(pos[heap[x].second],pos[heap[x>>1].second]);
	} 
}
inline void down(int x){
	while(1){
		if((x<<1)>tot)return;
		int y;
		if(heap[x<<1].first>heap[x<<1|1].first && (x<<1|1)<=tot)y=x<<1|1;
		else y=x<<1;
		if(heap[x].first>heap[y].first){
			swap(heap[x],heap[y]);
			swap(pos[heap[x].second],pos[heap[y].second]);
			x=y;
		}
		else return;
	}
}
inline void push(int x,int y){
	heap[++tot].first=x,heap[tot].second=y;
	up(tot);
}
inline void pop(){
	swap(heap[tot],heap[1]);
	pos[heap[1].second]=1;
	//cout<<heap[1];
	tot--;
	//cout<<"dsfsd";
	down(1);
}
int n,m,s;
struct node{
	int v,c,next;
}e[1000005];
inline void addedge(int u,int v,int c){
	e[++tot_edge].v=v;e[tot_edge].c=c;
	e[tot_edge].next=h[u];h[u]=tot_edge;
}
inline void dijkstrla(){
	memset(dis,0x3f,sizeof(int)*(n+1));
	push(0,s);
	dis[s]=0;
	vis[s]=1;
	while(tot){
		int u=heap[1].second;
		pop();
		for(int i=h[u];i;i=e[i].next){
			//cout<<e[i].v;
			//cout<<u<<" "<<h[u]<<endl;
			int v=e[i].v;
			if(dis[u]+e[i].c<dis[v]){
				//cout<<u<<" "<<h[u]<<endl;
				if(vis[v]){
					heap[pos[v]].first=dis[u]+e[i].c;
					up(pos[v]);
				}
				else{
					pos[v]=tot+1;
					push(dis[u]+e[i].c,v);
					vis[v]=1;
				}
				dis[v]=dis[u]+e[i].c;
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,c;
		u=read<int>();
		v=read<int>();
		c=read<int>();
		addedge(u,v,c);
	}
	dijkstrla();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}