Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = INT_MAX;
int n, m, s, mp[1005][1005], d[1005], u, v, w;
bool c[1005];
signed main() {
	cin >> n >> m >> s;
	memset(mp, 0x3f, sizeof(mp));
	for (int i = 1; i <= m; ++i) {
		scanf("%lld %lld %lld", &u, &v, &w);
		mp[u][v] = min(mp[u][v], w);
	}
	for (int i = 1; i <= n; ++i) d[i] = INF;
	for (int i = 1; i <= n; ++i) c[i] = false;
	
	d[s] = 0;
	
	for (int i = 1; i <= n; ++i) {
		int v = -1;
		for (int j = 1; j <= n; ++j) {
			if (c[j] == false && (v == -1 || d[v] > d[j]))
				v = j;	
		}
		if (v == -1) break;
		c[v] = true;
		for (int j = 1; j <= n; ++j)
			if (d[v] + mp[v][j] < d[j])
				d[j] = d[v] + mp[v][j];
	} 
	
	for (int i = 1; i <= n; ++i) printf("%lld ", d[i]);
	return 0;
}