#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, bool &ok) {
	vector <int> d, u;
	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));
	u.resize (n + 1, 0);
	d [sursa] = 0;
	q.push (make_pair (0, sursa));
	ok = true;
	while (ok && ! q.empty ()) {
		nod = q.top ();
		q.pop ();
		if (! u [nod.second]) {
			u [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 () {
	bool ok;
	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, ok);
	if (ok) {
		for (i = 2; i <= n; ++ i) {
			if (d [i] == (1 << 30)) {
				g << "0 ";
			}
			else {
				g << d [i] << " ";
			}
		}
		g << "\n";
	}
	else {
		g << "Ciclu negativ!\n";
	}
	f.close ();
	g.close ();
	return 0;
}