#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5e5 + 10;
const int INF = 1 << 31 - 1;

int n, m, s, l, r;
int dis[N], w[N], head[N], nxt[N], ver[N], cnt;

inline void add_edge(int, int);
inline void dijkstra(void);
inline void prep(void);

int main(void) {
	prep();
	dijkstra();
	for (int i = 1; i <= n; ++i) {
		if (dis[i] == 0x3f) printf("%d ", INF);
		else printf("%d ", dis[i]);
	}
	
	return 0;
}

inline void dijkstra(void) {
	priority_queue <pair <int, int> > q;
	bool vis[N] = {};
	
	for (int i = 1; i <= n; ++i) {
		dis[i] = 2147483647;
	}
	
	dis[1] = 0;
	q.push(make_pair(0, 1));
	
	while (!q.empty()) {
		int x = q.top().second;
		q.pop();
		
		if (!vis[x]) {
			vis[x] = true;
			
			for (int i = head[x]; i; i = nxt[i]) {
				int y = ver[i];
				
				if (dis[y] > dis[x] + w[i]) {
					dis[y] = dis[x] + w[i];
					q.push(make_pair(-dis[y], y));
				}
			}
		}
	}
}

inline void prep(void) {
	scanf("%d%d%d", &n, &m, &s);
	
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &l, &r, w + i);
		add_edge(l, r);
	}
}

inline void add_edge(int u, int v) {
	nxt[++cnt] = head[u];
	head[u] = cnt;
	ver[cnt] = v;
}