link

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n,m,u,minn=2147483647,nextadd,p;
struct s{
	int v,w;
};
s temp;
queue <int> S;
vector <s> map[100010];
int dist[100010];
bool used[100010];
int main(){
	memset(dist,11451400,sizeof(dist));
    cin>>n>>m>>p;
    for(int i=1;i<=m;i++){
        cin>>u>>temp.v;
        cin>>temp.w;
        map[u].push_back(temp);
    }
    S.push(1);
    while(S.size()<n){
    	minn=2147483647;
    	used[S.back()]=1;
    	if(S.back()==1){
    		for(int i=0;i<map[1].size();i++){
    			dist[map[1][i].v]=map[1][i].w;
			}
		}else{
			for(int i=0;i<map[S.back()].size();i++){
    			if((dist[S.back()]+map[S.back()][i].w) < (dist[map[S.back()][i].v]) ){
    				dist[map[S.back()][i].v] = (dist[S.back()]+map[S.back()][i].w);
				}
			}
		}	
    	for(int i=1;i<=n;i++){
    		if(dist[i]<=minn && used[i]==0){
    			minn=dist[i];
    			nextadd=i;
			}
		}
		S.push(nextadd);
	}
	cout<<0<<' ';
	for(int i=2;i<=n;i++) cout<<dist[i]<<' ';
}