#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

vector <int> dijkstra (int sursa, int n, vector <vector <pair <int, int> > > G) {
	vector <int> d;
	vector <bool> fin;
	priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;
	pair <int, int> nod;
	vector < pair <int, int> > :: iterator it;
	d.resize (n + 1, (1 << 30));
	fin.resize (n + 1, false);
	d [sursa] = 0;
	q.push (make_pair (0, sursa));
	while (! q.empty ()) {
		nod = q.top ();
		q.pop ();
		fin [nod.second] = true;
		for (it = G [nod.second].begin (); it != G [nod.second].end (); ++ it) {
			if (d [it->first] > d [nod.second] + it->second) {
				d [it->first] = d [nod.second] + it->second;
				q.push (make_pair (d [it->first], it->first));
			}
		}
	}
	return d;
}

int main () {
	int i, n, m, x, y, c;
	vector <vector <pair <int, int> > > G;
	ifstream f ("dijkstra.in");
	ofstream g ("dijkstra.out");
	f >> n >> m;
	G.resize (n + 1);
	for (i = 0; i < m; ++ i) {
		f >> x >> y >> c;
		G [x].push_back (make_pair (y, c));
	}
	vector <int> d = dijkstra (1, n, G);
	for (i = 2; i <= n; ++ i) {
		if (d [i] == (1 << 30)) {
			g << "0 ";
		}
		else {
			g << d [i] << " ";
		}
	}
	f.close ();
	g.close ();
	return 0;
}