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

#include<vector>
#include<queue>	
#include <bitset>

#include <fstream>
#include <iostream>

using namespace std;

#define INF 2147483647
#define MAX_N 50000

int M,N;

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

bool ciclu;

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

	queue<int> Q;
    bitset<MAX_N> in_queue(false);
	Q.push(0);
	in_queue[0]=true;
    
	int j,cost,vecin;
	vector < pair<int,int> >::iterator itvec;

	for(int i=1;i<=N;i++){
		if(Q.empty())
			break;
		
		while(!Q.empty()){
			j=Q.front(); Q.pop();
			in_queue[j] = false;
			
			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;
						if(!in_queue[vecin]){
							Q.push(vecin);
							in_queue[vecin]=true;
						}
					}
				}
			}
		}
	}

	if(Q.empty())
		return;

	while(!Q.empty()){
		j=Q.front(); Q.pop();	
		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;
					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;
}