#include<bits/stdc++.h>
using namespace std;
const int Maxm=2e5+5,Maxn=1e5+5;
struct Edge{
	int u,v,w;
	int next;
}e[Maxm];
int top;
struct Dist{
	int v,w;//到V的距离是W 
}pile[Maxm+Maxn];
int pt;//ptop
int head[Maxn];
int dis[Maxn];
bool vis[Maxn];
int n,m;
void reset(){
	for(int i=1;i<=n;i++) dis[i]=2e9;
}
void Add(int u,int v,int w){
	 top++;
	 e[top].u=u;
	 e[top].v=v;
	 e[top].w=w;
	 e[top].next=head[u];
	 head[u]=top;
	 return;
}
void Put(int v,int w){
	pile[++pt].v=v;
	pile[pt].w=w;
	int np=pt,fa=np/2;
	while(fa){
		if(pile[np].w>pile[fa].w) return;
		swap(pile[np],pile[fa]);
		np=fa;
		fa=np>>1;
	}
	return;
}
void Pop(){
	swap(pile[1],pile[pt]);
	pt--;
	int np=1,son=2;
	while(son<=pt){
		if(son<pt&&pile[son+1].w<pile[son].w) son++;
		if(pile[son].w<pile[np].w) return;
		swap(pile[np],pile[son]);
		np=son;
		son=np<<1;
	}
	return;
}
void Dijistra(int np){
	Put(np,0);
	while(pt){
		int v=pile[1].v,w=pile[1].w;
		Pop();
		if(vis[v]) continue;
		dis[v]=w;
		vis[v]=1;
		for(int i=head[v];i;i=e[i].next){
			if(vis[e[i].v]) continue;
			Put(e[i].v,w+e[i].w);
		}
	}
	return;
}
int main(){
	int u,v,w,s;
	scanf("%d%d%d",&n,&m,&s);
	reset();
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		Add(u,v,w);
	}
	Dijistra(s);
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}