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

vector<pair<int, int>> noduri[50001];
int dist[50001], cand_a_fost_schimbat[50001];

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

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

	for(int i=0; i<m; i++) {
		int de_unde, pana_unde, cat_costa;
		fin >> de_unde >> pana_unde >> cat_costa;

		// bag in lista nodului `de_unde` perechea (pana_unde, cat_costa)
		noduri[de_unde].push_back({pana_unde, cat_costa});
	}

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

	dist[1] = 0;
	for(int j=1; j<=n; j++) cand_a_fost_schimbat[j] = 0;

	// 2) de N-1 ori "relaxam muchiile"
	for(int runda=1; runda<=n-1; runda++) {

		for(int i=1; i<=n; i++) {
			if(cand_a_fost_schimbat[i] != runda-1) continue;

			int nr_muchii = noduri[i].size();
			for(int j=0; j<nr_muchii; j++) {
				int de_la = i,
					pana_la = noduri[i][j].first,
					cost = noduri[i][j].second;

				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;
					cand_a_fost_schimbat[pana_la] = runda;
				}
			}
		}
	}

	// 3) verificam daca avem cicluri negative
	for(int i=1; i<=n; i++) {
		for(auto muchie : noduri[i]) {
			if(dist[i] + muchie.second < dist[muchie.first]) {
				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;
}