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

using namespace std;

vector <int> what (int sursa, int n, vector <vector <pair <int, int> > > &G, bool &ok) {
	vector <int> d, len;
	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));
	len.resize (n + 1, 0);
	d [sursa] = 0;
	len [sursa] = 0;
	q.push (make_pair (0, sursa));
	ok = true;
	while (ok && ! q.empty ()) {
		nod = q.top ();
		q.pop ();
		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;
				len [it->first] = len [nod.second] + 1;
				q.push (make_pair (d [it->first], it->first));
				if (len [it->first] >= n) {
					ok = false;
					break;
				}
			}
		}
	}
	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 = what (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;
}