#include<bits/stdc++.h>
using namespace std;
struct edge {
	int to, dis, next;
}e[100010];
struct node {
	int dis, pos;
	bool operator <(const node &x)const {
		return x.dis < dis;
	}
};
priority_queue<node> q;
int head[100010], dis[100010], vis[100010];
int cnt, n, m, s;
void dijkstra() {
	dis[s] = 0;
	q.push((node){0, s});
	while(q.empty() == true) {
		node tmp = q.top();
		q.pop();
		int x = tmp.pos, d = tmp.dis;
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i = head[x]; i != 0; i = e[i].next) {
			if(dis[e[i].to] > dis[x] + e[i].dis) {
				dis[e[i].to] = dis[x] + e[i].dis;
				if(vis[e[i].to] == 0) {
					q.push((node){dis[e[i].to], e[i].to});
				}
			}
		}
	}
}
int main() {
	cin >> n >> m >> s;
	for(int i = 1;i <= n;i ++) {
		dis[i] = 0x7fffffff;
	}
	for(int i = 1;i <= m;i ++) {
		int u, v, d;
		cin >> u >> v >> d;
		cnt ++;
		e[cnt].dis = d;
		e[cnt].to = v;
		e[cnt].next = head[u];
		head[u] = cnt;
	}
	dijkstra();
	for(int i = 1;i <= n;i ++) {
		cout << dis[i] << " ";
	}
	return 0;
}