//Floyd

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

#define inf 0x3f3f3f3f
#define int long long
#define endl '\n'

int n, m, s;
int g[1010][1010];

signed main() {
	IOS;
	for (int i = 0;i < 1010;i++) {
		for (int j = 0;j < 1010;j++) {
			if (i == j) {
				g[i][j] = 0;
			}
			else {
				g[i][j] = inf;
			}
		}
	}
	cin >> n >> m >> s;
	for (int i = 1;i <= m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = w;
	}
	for (int k = 1;k <= n;k++) {
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	for (int i = 1;i <= n;i++) {
		if (g[s][i] >= inf) {
			cout << 2147483647 << ' ';
		}
		else {
			cout << g[s][i] << ' ';
		}
	}
	return 0;
}

//Fununugugu Code

我已经清楚 Floyd 无法满分通过此题，但是评测记录中出现了不应当出现的 RE 和 WA。望大佬解答