#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax = 5e4+10;
const int inf = 0x3F3F3F3F;
vector<vector<pair<int,long int>>> mat(nmax);
vector<int> distante(nmax),in_queue(nmax),numar_relaxari(nmax,0);
queue<int> q;
int n,m;
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2,cost;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2 >> cost;
		mat[nod_1].push_back(make_pair(nod_2,cost));
	}
};
bool bellman_ford(){
	fill(distante.begin(),distante.end(),inf);
	distante[1] = 0;
	q.push(1);
	in_queue[1] = 1;
	while(!q.empty()){
		int nod = q.front();
		q.pop();
		in_queue[nod] = 0;
		for(auto nod_aux : mat[nod]){
			if(distante[nod_aux.first] > distante[nod] + nod_aux.second ){
				distante[nod_aux.first] = distante[nod] + nod_aux.second;
				if(!in_queue[nod_aux.first]){
					q.push(nod_aux.first);
					in_queue[nod_aux.first] = 1;
					numar_relaxari[nod_aux.first]++;
					if(numar_relaxari[nod_aux.first] > n){
						return false;
					}
				}
			}
		}
		
	};
	return true;
}
int main(){
	read_input();
	if(bellman_ford()){
		for(int i = 2; i <=n; i++){
			fout << distante[i] << " ";
		}
	}else{
		fout << "Ciclu negativ!";
	};
	return 0;
}