#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define in "bellmanford.in"
#define out "bellmanford.out"
#define N 50005
#define y first
#define c second
#define oo 1 << 30

typedef pair <int, int> nod;
typedef unsigned u;

vector <nod> graf[N];
vector <int> nr (N, 0);
vector <int> d (N, oo);
queue <int> Q;
int n, m;

int NEG () {
	ofstream fout (out);
	fout << "Ciclu negativ!";
	fout.close();
	return 0;
}

int main () {
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		graf[x].push_back (nod (y, c));
	}
	fin.close();
	Q.push (1);
	d[1] = 0;
	while (Q.size()) {
		int x = Q.front();
		Q.pop();
		for (u i = 0; i < graf[x].size(); ++i)
			if (d[x] + graf[x][i].c < d[graf[x][i].y]) {
				d[graf[x][i].y] = d[x] + graf[x][i].c;
				nr[graf[x][i].y] ++;
				if (nr[graf[x][i].y] > n) {
					return NEG ();
				}
				Q.push (graf[x][i].y);
			}
	}
	ofstream fout (out);
	for (int i = 2; i <= n; ++i)
		fout << d[i] << " ";
	fout.close();
	return 0;
}