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

#include<vector>
#include<queue>
#include<set>

#include <fstream>
#include <iostream>

using namespace std;

int M,N;

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

bool ciclu;

#define INF 2147483647

//set<pair<int,int>> Q;

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

	//queue<int>* Q1=new queue<int>;
	//queue<int>* Q2=new queue<int>;

	set<int>* Q1=new set<int>;
	set<int>* Q2=new set<int>;

	vector<pair<int,int>>::iterator itvec; 
	set<int>::iterator itset; 

	int cost,vecin;

	for(int i=0;i<N;i++)
		Q1->insert(i);

	int j;
	for(int i=1;i<=N;i++){
		if(Q1->empty())
			break;
		
		//for(int j=0;j<N;j++){
		for(itset=Q1->begin(); itset!=Q1->end(); itset++){
			j=(*itset);
			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;
						//Q.insert(make_pair(vecin,true));
						Q2->insert(vecin);
					}
				}
			}
		}
		Q1->empty();
		set<int>* q=Q1;
		Q1=Q2;
		Q2=q;
	}

	if(Q1->empty())
		return;

	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;
}