#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
const int M=500000,N=100000,INF=1000000000,MAXN=2147483647;
struct edge{
	int u;
	int next;
	int v;
	int w;
}e[M+42];
struct node{
	int w;
	int now;
	bool operator < (const node &x) const{
		return w>x.w;
	}
};
priority_queue<node> q;
int head[N+42];
int dis[N+42];
bool vis[N+42];
int n,m,s,tot;
int u,v,w;
void pretreatment();
void add(int,int,int);
void dijkstra();
int main(){
	pretreatment();
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		if(dis[i]!=INF) printf("%d ",dis[i]);
		else printf("%d",INF);
	}
	return 0;
}
void pretreatment(){
	for(int i=0;i<=N;i++) head[i]=-1;
	for(int i=0;i<=N;i++) dis[i]=INF;
}
void add(int u,int v,int w){
	e[++tot].u=u;
	e[tot].next=head[u];
	e[tot].v=v;
	e[tot].w=w;
	head[u]=tot;
}
void dijkstra(){
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty()){
		node x=q.top();q.pop();
		int u=x.now;//记录堆顶的值 
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next){//堆顶的连边中尝试松弛 
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;//松弛 
				q.push((node){dis[v],v});
			}
		}
	}
}