rt

// 链式向前星存图
#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct Edge {
	int v, w, next;
}edge[200003];
struct Data {
	int dis, pos;
	bool operator < (const Data &x) const {
		return x.dis < dis;
	}
};
int n, m, s, cnt, vis[maxn], dis[maxn], head[maxn];
priority_queue<Data> q;
void add(int u, int v, int w) {
	cnt++;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push((Data){0, s});
	
	while (q.size()) {
		Data f = q.top();
		q.pop();
		int pos = f.pos;
		
		if (vis[pos]) {
			continue;
		}
		vis[pos] = 1;
		
		for (int i = head[pos]; i; i = edge[i].next) {
			int v = edge[i].v, w = edge[i].w;
			if (dis[v] > dis[pos] + w) {
				dis[v] = dis[pos] + w;
				if (vis[v] == 0) {
					q.push((Data){dis[v], v});
				}
			}
		}
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
		
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	
	dijkstra();
	
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
	return 0;
}

// 邻接表存图
#include <bits/stdc++.h>
#define maxn 100003
using namespace std;
struct GraphData {
	int v, w;
};
struct Data {
	int dis, u;
	bool operator < (const Data &x) const {
		return x.dis < dis;
	}
};
int n, m, s, vis[maxn], dis[maxn];
vector<GraphData> G[200003];
priority_queue<Data> q;
void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push((Data){0, s});
	
	while (q.size()) {
		Data f = q.top();
		q.pop();
		int u = f.u;
		
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v, w = G[u][i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (vis[v] == 0) {
					q.push((Data){dis[v], v});
				}
			}
		}
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
		
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back((GraphData){v, w});
	}
	
	dijkstra();
	
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
	return 0;
}