#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 5e4;
const int INF = 2e9;

int N, M;

struct Edge {
	int to, cost;
};

queue<int> q;
bool inQ[NMAX + 1];
int cnt[NMAX + 1];
vector<Edge> adj[NMAX + 1];
int dist[NMAX + 1];

int main() {
	fin >> N >> M;

	for(int i = 1; i <= M; i++) {
		int A, B, C;
		fin >> A >> B >> C;

		adj[A].push_back(Edge{B, C});
	}

	for(int i = 1; i <= N; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	q.push(1);
	inQ[1] = 1;

	while(!q.empty()) {
		int u = q.front();
		q.pop();
		inQ[u] = 0;

		for(const Edge edge: adj[u]) {
			if(dist[edge.to] > dist[u] + edge.cost) {
				dist[edge.to] = dist[u] + edge.cost;

				cnt[edge.to]++;
				if(cnt[edge.to] > N) {
					fout << "Ciclu negativ!\n";
					return 0;
				}

				if(!inQ[u]) {
					q.push(edge.to);
					inQ[edge.to] = 1;
				}
			}
		}
	}

	for(int i = 2; i <= N; i++) {
		if(dist[i] == INF) {
			dist[i] = 0;
		}
		fout << dist[i] << " ";
	}
	return 0;
}