#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define nmax 50005
#define inf 1<<30
using namespace std;

struct nod {
	int nume;
	int cost;
};

vector <nod> v[nmax];
nod T;

int n, m;

int updates[nmax], best[nmax];
queue <int> q;

void bellmanford() {
	int curent, vecin;

	while(!q.empty()) {
		curent = q.front();
		q.pop();

		for(int i=0; i<v[curent].size(); i++) {
			//costul nou pe care l-as putea construi este best[curent] + muchie(curent, vecin)
			//adica best[curent] + v[curent][i].cost
			if(best[curent] + v[curent][i].cost < best[ v[curent][i].nume ]) {
				best[ v[curent][i].nume ] = best[curent] + v[curent][i].cost;
				q.push( v[curent][i].nume );
				updates[ v[curent][i].nume ]++;

				if(updates[ v[curent][i].nume ] >= n) return;	//am ciclu de cost negativ
			}
		}
	}
}

int main() {
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int i, j;

	f>>n>>m;
	
	for(i=1; i<=n; i++) {
		best[i] = inf;
		updates[i] = 0;
	}
	best[1] = 0;
	q.push(1);
	
	for(i=1; i<=m; i++) {
		f>>j>>T.nume>>T.cost;
		v[j].push_back(T);
	}

	bellmanford();

	for(i=1; i<=n; i++)
		if(updates[i] >= n) {
			g<<"Ciclu negativ!\n";
			return 0;
		}
	

	for(i=2; i<=n; i++) g<<best[i]<<" ";
	g<<"\n";


	return 0;
}