#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0, f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

struct edge{
	ll to, next, dis;
};
edge e[1000086];
ll n, m, s, head[1086], u, v, w, tot, cnt, dis[100086], vis[100086];
queue<ll> q;
inline void spfa(ll s){
	memset(dis, 0x3f3f3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[s] = 0;
	vis[s] = true;
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		vis[u] = false;
		q.pop();
		for(int i=head[u];i;i=e[i].next){
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].dis){
				dis[v] = dis[u] + e[i].dis;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

inline void add(ll u, ll v, ll w){
	tot++;
	e[tot].next = head[u];
	e[tot].to = v;
	e[tot].dis = w;
	head[u] = tot;
}

int main(){
	n = read(), m = read(), s = read();
	for(int i=1;i<=m;++i){
		u = read(), v = read(), w = read();
		add(u, v, w);
	}
	spfa(1);
	for(int i=1;i<=n;++i){
		cout<<dis[i]<<" ";
	}
	return 0;
}