#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define mmax 250005
#define inf (1<<30)
using namespace std;

vector <int> v[nmax], w[nmax];
queue <int> q;

int n, m, a, b, c, best[nmax], pre[nmax], updates[nmax];
bool cycle = false, inQ[nmax];

void bellmanford() {
	for(int i=2; i<=n; i++) best[i] = inf;
	q.push(1);
	inQ[1] = true;

	while(!q.empty()) {
		int x = q.front();
		q.pop();
		inQ[x] = false;

		for(int i=0; i<v[x].size(); i++)
			if(best[x] + w[x][i] < best[v[x][i]]) {
				best[v[x][i]] = best[x] + w[x][i];
				pre[v[x][i]] = x;
				updates[v[x][i]]++;

				if(!inQ[v[x][i]]) {
					inQ[v[x][i]] = true;
					q.push(v[x][i]);
				}

				if(updates[v[x][i]] > n) { cycle = true; return; }
			}
	}
}			

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

	f>>n>>m;
	for(int i=1; i<=m; i++) {
		f>>a>>b>>c;
		v[a].push_back(b);
		w[a].push_back(c);
	}

	bellmanford();

	if(cycle) g<<"Ciclu negativ!";
	else for(int i=2; i<=n; i++) g<<best[i]<<" ";

	g<<"\n";
	return 0;
}