#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> ii;

int main() {
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	int n, m;
	fin >> n >> m;
	vector<ii> adjl[n];
	for (int i=0, u, v, c; i<m; ++i) {
		fin >> u >> v >> c;
		adjl[--u].push_back(ii(--v, c));
	}
	vector<int> cost(n, 1<<30);
	cost[0]=0;
	for (int i=0; i<n-1; ++i) {
		for (int j=0; j<n; ++j) {
			for (vector<ii>::iterator it=adjl[j].begin(); it!=adjl[j].end(); ++it) {
				cost[it->first] = min( cost[it->first], cost[j] + it->second );
			}
		}
	}
	for (int j=0; j<n; ++j) {
		for (vector<ii>::iterator it=adjl[j].begin(); it!=adjl[j].end(); ++it) {
			if ( cost[it->first] > cost[j] + it->second ) {
				fout << "Ciclu negativ!";
				return 0;
			}
		}
	}
	for (int i=1; i<n; ++i) {
		fout << cost[i] << ' ';
	}
	return 0;
}