#include <fstream>
#include <queue>
#include <vector>
using namespace std;

struct muc{
	int dest, cost; };

int main(){
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int n, m;
	f >> n >> m;
	vector<vector<muc> > graf(n);
	vector<int> dist(n, 1000000000);
	dist[0] = 0;
	for(int i = 0, a, b, c; i < m; ++i){
		f >> a >> b >> c;
		--a, --b;
		graf[a].push_back({b, c}); }
	queue<int> de_viz_cur, de_viz_next;
	for(int i = 0; i < n; ++i){
		de_viz_cur.push(i); }
	vector<bool> in_queue_cur(n, true), in_queue_next(n, false);
	for(int i = 0; i < m-1; ++i){
		while(!de_viz_cur.empty()){
			const int cur = de_viz_cur.front();
			de_viz_cur.pop();
			in_queue_cur[cur] = false;
			for(const auto next : graf[cur]){
				if(dist[next.dest] > dist[cur] + next.cost){
					dist[next.dest] = dist[cur] + next.cost;
					if(!in_queue_next[next.dest]){
						in_queue_next[next.dest] = true;
						de_viz_next.push(next.dest); } } } }
		swap(de_viz_cur, de_viz_next);
		swap(in_queue_cur, in_queue_next); }
	bool ciclu_negativ = false;
	for(int i = 0; i < n && !ciclu_negativ; ++i){
		for(const auto next : graf[i]){
			if(dist[next.dest] > dist[i] + next.cost){
				ciclu_negativ = true; } } }
	if(ciclu_negativ){
		g << "Ciclu negativ!"; }
	else{
		for(int i = 1; i < n; ++i){
			g << dist[i] << ' '; } }
	
	return 0; }