#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 5e5+9;
int n, m, s;
 
struct edge{
	int v;
	ll w;
	int nxt;
}e[N];

int head[N], cnt = -1;

inline void add(int u, int v, int  w){
	e[++cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
} 

ll dit[N];
int vis[N];

priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q; 

int main() {
	cin>>n>>m>>s;
	memset(head, -1, sizeof(head));
	for (int i = 1; i <= m; ++i) {
		ll u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for (int i = 1; i <= n; ++i) dit[i] = (1 << 31LL) - 1; 
	dit[s] = 0; 
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().second; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i !=  -1; i = e[i].nxt) {
			int v = e[i].v;
			if (dit[v] > dit[u] + e[i].w) {
				dit[v] = dit[u] + e[i].w;			
				if (!vis[u]) q.push({dit[v], v});
			}
		}
	} 
	for (int i = 1; i <= n; ++i ){
		printf("%lld ",dit[i]);
	}
	return 0;
}