#include <bits/stdc++.h>
using namespace std;
int n, m, s;
struct node {
	int v, w;
}temp;
vector<node> u[114514];
bool vis[114514];
int Min = 1e9,target,dis[114514];
int main() {
	cin >> n >> m >> s;
	for (int i = 1, x, y, z; i <= m; i++) {
		cin >> x >> y >> z;
		temp.v = y, temp.w = z;
		u[x].push_back(temp);
		
	}memset(dis,1e9,sizeof(dis));
	/*for (int i = 1; i <= n; i++) {
		for (int j = 0; j < u[i].size(); j++) {
			cout << u[i][j].v << " ";
		}cout << endl;
	}*/
	dis[s] = 0;
	for (int k = 1; k <= n;k++) {
		Min = 1e9, target = 0;
		for (int i = 1; i <= n; i++) {
			if (Min > dis[i] && !vis[i]) {
				Min = dis[i], target = i;
			}
		}
		if (target == 0)break;vis[target] = true;
		for (int j = 0; j < u[target].size(); j++) {
			int len = u[target][j].w,to=u[target][j].v;
			if (dis[to] > dis[target] + len) {
				dis[to] = dis[target] + len;
			}
		}
	}for (int i = 1; i <= n; i++) {
		if (dis[i] == 1e9)cout << pow(2,31)-1 << " ";
		else cout << dis[i] << " ";
	}
	return 0;

}