#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n, m, s, x, y, z;
int a[10005][10005], d[10005];
bool t[10005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> z;
		if(!a[x][y]){
			a[x][y]=0x3f3f3f3f;
		}
		a[x][y] = min(a[x][y],z);
	}
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	for (int i = 1; i <= n; i++) {
		int mi = -1; 
		for (int j = 1; j <= m; j++) {
			if (!t[j] && (mi == -1 || d[mi] > d[j])) {
				mi = j;
			}
		}
		t[mi] = 1;
		for (int k = 1; k <= n; k++) {
			if (!t[k] && a[mi][k] != 0 && d[k] > d[mi] + a[mi][k]) {
				d[k] = d[mi] + a[mi][k];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0x3f3f3f3f) {
			long long l = pow(2, 31) - 1;
			cout << l << " ";
		} else {
			cout << d[i] << " ";
		}
	}
	return 0;
}