#include <bits/stdc++.h>
#define MAXN 10005
#define MAXM 500005
#define INF 0x7fffffff
using namespace std;
struct EDGE {
	int t, n, w;
}e[MAXM];
int n, m, s, cnt, dis[MAXN], head[MAXM];
priority_queue<int> q;
bool vis[MAXN];
inline void addnode(int a, int b, int w) {
	e[++cnt].t = b;
	e[cnt].w = w;
	e[cnt].n = head[a];
	head[a] = cnt;
}
int main() {
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		addnode(a, b, w);
	}
	for(int i = 1; i <= n; i++)
		dis[i] = INF;
	dis[s] = 0;
	q.push(-s);
	while(!q.empty()) {
		int p = -q.top();
		q.pop();
		if(vis[p])
			continue;
		vis[p] = true;
		for(int i = head[p]; i; i = e[i].n) {
			int t = e[i].t, w = e[i].w;
			dis[t] = min(dis[t], dis[p] + w);
			if(!vis[t])
				q.push(-t);
		}
	}
	for(int i = 1; i <= n; i++)
		cout << dis[i] << " ";
	return 0;
}