#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500001, inf = 0x3f;
struct sdsd {
	int from, to, nxt;
	ll w;
} edge[N];
int n, m, u, v, s, W;
ll dis[N];
bool vis[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;

int cnt, head[N];
void add_edge(int from, int to, ll w) {
	edge[++cnt] = {from, to, head[from], w};
	head[from] = cnt;
}

void dij() {
	memset(dis, inf, sizeof(dis));
	q.push(make_pair(0, s));
	dis[s] = 0;
	while (!q.empty()) {
		int a = q.top().second;
		q.pop();
		if (!vis[a]) {
			vis[a] = 1;
			for (int i = head[a]; i; i = edge[i].nxt) {
				int t = edge[i].to;
				if (dis[a] + edge[i].w < dis[t]) {
					dis[t] = dis[a] + edge[i].w;
					q.push(make_pair(dis[t], t));
				}
			}
		}

	}
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%lld", &u, &v, &W);
		add_edge(u, v, W);
	}
	dij();
	for (int i = 1; i <= n; i++) {
		printf("%lld ", dis[i]);
	}
	return 0;
}