#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#define DN 50005
#define INF 1000000000

using namespace std;

vector<pair<int, int> > graph[DN];
int inqueue[DN], cost[DN], visited[DN];

int main() {
	int n, m, a, b, c;
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		fin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}
	
	queue<int> q;
	q.push(1);
	inqueue[1] = 1;
	for (int i = 2; i <= n; ++i)
		cost[i] = INF;
		
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		inqueue[node] = 0;
		visited[node] ++;
		for (int i = 0; i < graph[node].size(); ++i) {
			int neighbour = graph[node][i].first;
			if (cost[neighbour] <= cost[node] + graph[node][i].second)
				continue;
			cost[neighbour] = cost[node] + graph[node][i].second;
			if (inqueue[neighbour] || visited[node] == n)
				continue;
			inqueue[neighbour] = 1;
			q.push(neighbour);
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < graph[i].size(); ++j) {
			if (cost[graph[i][j].first] > cost[i] + graph[i][j].second) {
				fout << "Ciclu negativ!";
				return 0;
			}
		}
	}
	
	for (int i = 2; i <= n; ++i)
		fout << cost[i] << " ";
	return 0;
}