#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 500010
#define INF 0x3f3f3f

using namespace std;

inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

int n;
int m;
int s;
int head[MAXN];
int cnt;
int dis[MAXN];
bool visit[MAXN];

struct Edge{
	int v;
	int w;
	int next;
	
	void add(){
		int u;
		cnt++;
	 	u=read();
		v=read();
		w=read();
		next=head[u];
		head[u]=cnt;
	}
	
}edge[MAXN];

struct node{
	int dis;
	int pos;
	bool operator < (const node &x)const{
		return x.dis<dis;
	}
};

std::priority_queue<node> q; 

void init(){
	memset(visit,false,sizeof(visit));
	memset(head,0,sizeof(head));
	memset(dis,INF,sizeof(dis));
}

void dijkstra(int s){
	q.push((node){0,s});
	dis[s]=0;
	while(!q.empty()){
		node top=q.top() ;
		q.pop() ;
		int disn=top.dis ;
		int posn=top.pos ;
		if(visit[posn]){
			continue;
		}
		visit[posn]=true;
		for(int i=head[posn];i;i=edge[i].next ){
			int t=edge[i].v;
			if(dis[t]>dis[posn]+edge[i].w){
				dis[t]=dis[posn]+edge[i].w ;
				if(!visit[t]){
					q.push((node){dis[t],t}); 
				}
			}
		}
	}
	
}

int main(){
	init();
	n=read();
	m=read();
	s=read();
	for(int i=1;i<=m;i++){
		edge[i].add() ;
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}