#include <fstream>
#include <vector>
#include <queue>
#define DIM 50005
#define vint vector< pair<int, int> >::iterator
#define infile "bellmanford.in"
#define outfile "bellmanford.out"

using namespace std;

const int INF = 2000000000;

ifstream f(infile);
ofstream g(outfile);

vector< pair<int, int> > L[DIM];

queue<int> Q;

int n, m, a, b, c;

int D[DIM], ap[DIM];

bool ok[DIM];

int main() {
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> a >> b >> c;
		L[a].push_back(make_pair(b, c));
	}
	for (int i = 2; i <= n; ++i)
		D[i] = INF;
	Q.push(1);
	while (!Q.empty()) {
		int nod = Q.front();
		Q.pop();
		ok[nod] = 0;
		for (vint it = L[nod].begin(); it != L[nod].end(); ++it)
		if (D[it->first] > D[nod] + it->second) {
			D[it->first] = D[nod] + it->second;
			++ap[it->first];
			if (ap[it->first] == n) {
				g << "Ciclu negativ!";
				return 0;
			}
			if (!ok[it->first]) {
				ok[it->first] = 1;
				Q.push(it->first);
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		g << D[i] << " ";


	return 0;
}

//This room. This bullet. There's a bullet for everyone. And a time. And a place. Yes... maybe this is how it has to be. - 47