#include<bits/stdc++.h>
using namespace std; 
struct edge{
	int to;
	int w;
};
long long d[100010];bool in[100010]; 
vector<edge> e[100010];

int main(){
	int n,m,s;
	cin >> n >> m >> s;
	for(int i = 1; i <= n; i++){
		d[i] = (1LL<<31) - 1;
	}
	for(int i = 1; i < m; i++){
		int u,v,w;
		cin >> u >> v >> w;
		e[u].push_back((edge){v,w});
	}
	d[s] = 0;
	for(int t = 1; t <= n; t++){
		int x;
		long long mi=1LL<<31;
		for(int i = 1; i <= n; i++){
			if(!in[i]&&d[i] < mi){
				mi = d[i];
				x = i;
			}
		}
		in[x] = true;
		for(int j = 0; j < e[x].size(); j++){
			int v = e[x][j].to,w = e[x][j].w;
			if(d[x] + w < d[v]){
				d[v] = d[x] + w;
			}
		}
	} 
	for(int i =  1; i <= n; i++){
		cout <<d[i]  << " ";
	}
	return 0;
}

求助