#include<bits/stdc++.h>
using namespace std;
#define N 100005 
#define M 200005 
int ver[M],nexxt[M],val[M],head[N],idx,dis[N],n,m,s,u,v,w,vis[N];
struct node{
	int dis,pos;
	bool operator<(const node &x)const{
		return x.dis < dis;
	}
};
void add(int u,int v,int w){
	ver[++idx] = v;
	val[idx] = w;
	nexxt[idx] = head[u];
	head[u] = idx;
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d",&u,&v,&s);
		add(u,v,s);
	}
	dis[s] = 0;
	priority_queue<node>q;
	q.push((node){0,s});
	while(q.size()){
		node tmp = q.top();
		q.pop();
		if(vis[tmp.pos]) continue;
		vis[tmp.pos] = 1;
		for(int i = head[tmp.pos];i;i = nexxt[i]){
			if(!vis[i]){
			if(dis[ver[i]] > dis[tmp.pos]+val[i]){
				dis[ver[i]] = dis[tmp.pos]+val[i];
				q.push((node){dis[ver[i]],ver[i]}); 
			}
		}
		}
	} 
	for(int i = 1; i <= n; i++){
		printf("%d ",dis[i]);
	}
	return 0;
}