#include<stdio.h>
#include<stdlib.h>

#include <cstring>
#include<vector>

#include <fstream>
#include <iostream>

using namespace std;

int M,N;

vector<pair<int,int>> L[50000];
int D[50000];

bool ciclu;

#define INF 2147483647
//#define INF 1000000000

void bellmanford(){
	for(int i=0;i<N;i++)
		D[i]=INF; 
	D[0]=0; 

	vector<pair<int,int>>::iterator itvec; 
	int cost,vecin;

	for(int i=1;i<=N;i++){
		for(int j=0;j<N;j++){
			if(D[j]<INF){
				for (itvec = L[j].begin(); itvec != L[j].end(); ++itvec) {
					vecin=(*itvec).first;
					cost=(*itvec).second;
					if((D[j] + cost) < D[vecin])
						D[vecin]=D[j]+cost;
				}
			}
		}
	}

	for(int j=0;j<N;j++){
		for (itvec = L[j].begin(); itvec != L[j].end(); ++itvec) {
			vecin=(*itvec).first;
			cost=(*itvec).second;
			if((D[j] + cost) < D[vecin]){
				D[vecin]=D[j]+cost;
				ciclu=true;
				return;
			}
		}
	}
	
}

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

int main(){
		
	fin >> N >> M;

	int x,y,cost;

	for(int i=0;i<M;i++){
		fin >> x >> y >> cost;
		L[x-1].push_back(make_pair(y-1,cost));	
	}

	bellmanford();

	if(ciclu)
		fout << "Ciclu negativ!\n";
	else{
		for(int i=1;i<N;i++)
			fout << D[i] << " ";
	}

	fin.close();
    fout.close();

	return 0;
}