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

struct muchie { // muchie de la a la b cu cost c
	int a, b, c;
};

muchie muchii[250000];
int dist[50001];

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

	int n, m;
	fin >> n >> m;

	for(int i=0; i<m; i++) {
		fin >> muchii[i].a >> muchii[i].b >> muchii[i].c;
	}

	// bellman ford
	// 1) initializam dist cu infinit
	for(int i=1; i<=n; i++) {
		dist[i] = 999999999;
	}

	dist[1] = 0;

	// 2) de N-1 ori "relaxam muchiile"
	for(int i=1; i<=n-1; i++) {
		for(int j=0; j<m; j++) {
			// relaxam muchia j
			int de_la = muchii[j].a,
				pana_la = muchii[j].b,
				cost = muchii[j].c;
			if(dist[de_la] + cost < dist[pana_la]) {
				// am gasit un drum mai bun pana la nodul `pana_la`
				dist[pana_la] = dist[de_la] + cost;
			}
		}
	}

	// 3) verificam daca avem cicluri negative
	for(int i=0; i<m; i++) {
		int de_la = muchii[i].a,
			pana_la = muchii[i].b,
			cost = muchii[i].c;
		if(dist[de_la] + cost < dist[pana_la]) {
			fout << "Ciclu negativ!" << endl;
			return 0;
		}
	}

	// Daca nu am ciclu negativ e ok si afisam distantele:
	for(int i=2; i<=n; i++) {
		fout << dist[i] << " ";
	}

	fout << endl;

	return 0;
}