#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x7fffffff;

int n, m, s;
struct node {
	int u;
	long long dis;
	bool operator < (const node &cmp) const {
		return dis > cmp.dis;
	}
};
vector<node> g[N];
priority_queue<node> q;
long long dis[N], vis[N];

void dijkstra() {
	for (int i = 1; i <= n; i++) dis[i] = INF;
	dis[s] = 0;
	q.push({s, 0});
	while(!q.empty()) {
		int u = q.top().u; q.pop();
		vis[u] = 1;
		for (auto v : g[u]) {
			if (dis[v.u] > dis[u] + v.dis) {
				dis[v.u] = dis[u] + v.dis;
				if (!vis[v.u]) q.push({v.u, dis[v.u]});
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({v, w});
	}
	dijkstra();
	for (int i = 1; i <= n; i++) {
		printf("%lld ", dis[i]);
	}
	return 0;
}