#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector < pair<int, int> > v[50001];
queue <int> coada;
int N, M;
int distanta[50001], n_viz[50001];
bool in_coada[50001];

int main()
{
	int nod_curent, dest, cost;
	int a,b,c;
	f >> N >> M;
	for(int i = 0; i < M; i++) {
		f >> a >> b >> c;
		v[a].push_back( make_pair(b, c));
	}
	coada.push(1);
	in_coada[1] = 1;
	for(int i = 2; i <= N; i++) {
		distanta[i] = 0x7fffffff;
	}
	while(coada.size() != 0) {
		nod_curent = coada.front();
		coada.pop();
		in_coada[nod_curent] = 0;
		for(int i = 0; i < v[nod_curent].size(); i++) {
			dest = v[nod_curent][i].first;
			cost = v[nod_curent][i].second;
			if(distanta[dest] > distanta[nod_curent] + cost) {
				distanta[dest] = distanta[nod_curent] + cost;
				if(in_coada[dest] == 0){
					if(n_viz[dest] > N) {
						g<<"Ciclu negativ!";
						return 0;
					}
					in_coada[dest] = 1;
					n_viz[dest]++;
					coada.push(dest);
				}
			}
		}
	}
	for(int i = 2; i <= N; i++) {
		g << distanta[i] << " ";
	}
}