【违规紫衫】WA+TLE+MLE

//
#define debug
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int Maxn = 5e3 + 1;
const ll INF = 1145141919810;
ll a[Maxn][Maxn];
int n, m, s;

int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> s;
  for(int i = 1; i <= n; i++){
  	for(int j = 1; j <= n; j++){
  		a[i][j] = INF;
		}
	}
  for(int i = 1; i <= m; i++){
  	int x, y, z;
  	cin >> x >> y >> z;
  	a[x][y] = a[y][x] = z;
	}
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(k != i && i != j && j != k && a[i][j] > a[i][k] + a[k][j]){
					a[i][j] = a[i][k] + a[k][j];
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(i == s){
			cout << "0 ";
		}
		else{
			cout << (a[s][i] == INF ? 2147483647 : a[i][s]) << ' ';
		}
	}
	cout << endl;
	return 0;
}