#include <bits/stdc++.h>

#define INF 10000000

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct edge{
	int dist, nod;
};

vector <edge> v[250006];
int n, m, a, b, c, d[250006]; bool viz[100006];
edge x; queue <edge> q;

int main(){
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> a >> b >> c;
		x.dist = c;
		x.nod = b;
		v[a].push_back(x);
	}
	for(int i = 1; i <= n; i++) d[i] = INF;
	for(int i = 0; i < v[1].size(); i++) q.push(v[1][i]), d[v[1][i].nod] = v[1][i].dist;
	while(!q.empty()){
		x = q.front();
		q.pop();
		for(int i = 0; i < v[x.nod].size(); i++){
			q.push(v[x.nod][i]);
			if(d[x.nod] + v[x.nod][i].dist < d[v[x.nod][i].nod]) 
				d[v[x.nod][i].nod] = d[x.nod] + v[x.nod][i].dist;
		}
	}
	for(int i = 2; i <= n; i++)
        if (d[i] == INF) out << "0\n";
        else out << d[i] << " ";
	return 0;
}