#include <bits/stdc++.h>
#define N 50005

#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<uint, uint>
#define VI vector<int>

using namespace std;

const uint INF = -1;
	
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

uint S = 1;			// the starting node
vector<puu> g[N]; 	// se = next node, fi = distance
uint dist[N];

// Computes the distance from S to all the other nodes, does not work with negative distances
void dijkstra(){
    priority_queue<puu, vector<puu>, greater<puu>> que;
    memset(dist, 0xff, sizeof(dist));
    dist[S] = 0;
    que.push({0, S});
	
    while(!que.empty()){
        puu p = que.top(); que.pop();
        if(p.fi != dist[p.se]) continue;

        for(puu e : g[p.se])
            if(p.fi + e.fi < dist[e.se]){
                dist[e.se] = p.fi + e.fi;
                que.push({dist[e.se], e.se});
            }
    }
}
	
int main(){
	uint m, n;
	fin >> n >> m;

	while(m --){
		uint x, y, d;
		fin >> x >> y >> d;
		g[x].pb({d, y});
	}

	dijkstra();
	for(uint i = 2; i <= n; i ++)
		if(dist[i] == INF)	fout << "0 ";
		else 				fout << dist[i] << ' ';
}