#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define let(X, A) typeof(A) X(A)
#define ech(It, A) for (let( It, A.begin() ); It != A.end(); ++It)
const int inf = 1<<29;

struct edge {
	int w;
	int v;
	edge ( int w, int v ) : w(w), v(v) {}
};

int main() {
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	int n, m;
	fin >> n >> m;
	vector<edge> adjl[n+1];
	for (int u, v, w, i=0; i<m; ++i) {
		fin >> u >> v >> w;
		adjl[u].push_back( edge(w, v) );
	}

	vector<int> dist( n+1, inf );
	dist[1] = 0;
	queue<int> Q;
	Q.push(1);
	vector<bool> inQ(n+1);
	inQ[1] = true;
	vector<int> cnt_inQ(n+1);

	while (!Q.empty()) {
		int v = Q.front();
		Q.pop();
		inQ[v] = false;

		ech( it, adjl[v] ) {
			if (dist[it->v] > dist[v] + it->w) {
				dist[it->v] = dist[v] + it->w;

				if (!inQ[it->v]) {
					if (++cnt_inQ[it->v] == n) {
						fout << "Ciclu negativ!";
						return 0;
					}
					Q.push(it->v);
					inQ[it->v] = true;
				}
			}
		}
	}

	for (int i=2; i<=n; ++i) {
		fout << dist[i] << ' ';
	}
	return 0;
}