#include <bits/stdc++.h>
using namespace std;

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

const int INF = 1e9;
const int MAXN = 50001;

vector<pair<int,int>> G[MAXN];
int n, d[MAXN], rep[MAXN];

void BellmanFord(int start) {
	for(int i = 1; i <= n; i++)
		d[i] = INF;
	
	queue<int> Q;
	Q.push(start);
	rep[start] = 1;
	d[start] = 0;
	
	while(!Q.empty()) {
		int node = Q.front();
		Q.pop();
		
		for(auto nxt : G[node])
			if(d[node] + nxt.second < d[nxt.first]) {
				d[nxt.first] = d[node] + nxt.second;
				Q.push(nxt.first);
				
				rep[nxt.first]++;
				if(rep[nxt.first] > n) {
					fout << "Ciclu negativ\n";
					return;
				}
			}
	}
	
	for(int i = 2; i <= n; i++)
		fout << (d[i] == INF ? -1 : d[i]) << " ";
	fout << "\n";
}

int main() {
	int m, a, b, c;
	
	fin >> n >> m;
	while(m--) {
		fin >> a >> b >> c;
		G[a].emplace_back(b, c);
	}
	
	BellmanFord(1);
	
	return 0;
}