#include <cstdio>
using namespace std;
const int maxn=2e5+10;
struct edge{
	int u,v,w;
}e[maxn<<2];
int tail[maxn],cnt;
void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].u=tail[u];
	tail[u]=cnt;
}
struct Heap{
	int siz;
	struct node{
		int id,w;
	}h[maxn<<1];
	void swap(node a,node b){
		node c=a;
		a=b,b=c;
	}
	void push(int id,int w){
		siz++;
		h[siz].id=id,h[siz].w=w;
		int u=siz;
		while(u){
			int v=u>>1;
			if(h[u].w<h[v].w) swap(h[u],h[v]);
			else break;
			u=v;
		} 
	}
	void pop(){
		swap(h[1],h[siz]);
		siz--;
		int u=1;
		while((u<<1)<=siz){
			int v=u<<1;
			if(v+1<=siz && h[v].w>=h[v+1].w) v++;
			if(h[u].w>h[v].w) swap(h[u],h[v]);
			else break;
			u=v;
		}
	}
	bool empty(){
		if(siz<=0) return 1;
		else return 0;
	}
	int top(){
		return h[1].id;
	}
}q;
int n,m,s;
int dis[maxn],vis[maxn];
void Dij(int s){
	q.push(s,0);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty()){
		int u=q.top();
		q.pop();
		vis[u]=1;
		for(int i=tail[u];i;i=e[i].u){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]){
					q.push(v,dis[v]);
					vis[v]=1;
				}
			}
		}
		vis[u]=0;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;i++){
		dis[i]=1e9+114;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	Dij(s);
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}