#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <map>
#include <utility>
#include <queue>
#include <cstring>
#include <climits>
#include <fstream>
using namespace std;

typedef long long LL;
typedef LL T;
typedef vector<T> VT;
typedef pair<T,T> TT;
typedef vector<TT> VTT;
typedef vector<vector<T> > VVT;

// Graph
typedef vector<VTT> AdjList;

// defines
#define INFINITY LLONG_MAX


/*
 * Bellman-Ford Algorithm
 * Single Source Shortest Path
 * Works on Graphs with negative edges
 * If Graph contains a negative cycle then Bellman-Ford can detect it.
 * Complexity: O(|V| * |E|)
 * Improvement:
 * For relaxation use only nodes that were improved.
 * Complexity: O(|V| * |E| * log(|V|))¢
 */
bool bellman(const AdjList& G, const int s, vector<LL>& dist, vector<int>& parent) {

	int N = G.size();
	dist.resize(N, INFINITY);
	parent.resize(N, -1);
	queue<int> Q;
	map<int, bool> in_queue;

	// compute shortest paths from s to all vertices
	dist[s] = 0;
	Q.push(s);
	in_queue[s] = true;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		in_queue[u] = false;
		for (int j=0; j<G[u].size(); ++j) {
			int v = G[u][j].first;
			LL w = G[u][j].second;
			if (dist[u] != INFINITY && dist[u] + w < dist[v]) {
				if (in_queue.find(v) == in_queue.end() || !in_queue[v]) {
					dist[v] = dist[u] + w;
					parent[v] = u;
					Q.push(v);
					in_queue[v] = true;
				}
			}
		}
	}

	// check for negative cycles
	for (int u=0; u<G.size(); ++u) {
		for (int j=0; j<G[u].size(); ++j) {
			int v = G[u][j].first;
			LL w = G[u][j].second;
			if (dist[u] != INFINITY && dist[u] + w < dist[v]) { // contains negative cycle
				return true;
			}
		}
	}
	return false;
}


int main (int argc, char** argv) {


	//ifstream fin(argv[1]);
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");

	int N, M;
	fin >> N >> M;
	AdjList G(N, VTT());
	for (int i=0; i<M; ++i) {
		int x, y;
		LL c;
		fin >> x >> y >> c;
		x--, y--;
		G[x].push_back(make_pair(y, c));
	}

	vector<LL> dist;
	vector<int> parent;
	if (bellman(G, 0, dist, parent)) {
		fout << "Ciclu negativ!";
	} 
	else {
		for (int i=1; i<N; ++i) {
			fout << dist[i] << " ";
		}
	}



	return 0;
}