#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];
vector <int> D(MAX_N, INF); 
vector<int> cnt_in_queue(MAX_N,0);

bool ciclu;

void bellmanford(){
	for(int i=1;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;
		
	while(!Q.empty() && !ciclu){
		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]){
						if (cnt_in_queue[vecin] > N){
							ciclu = true; 
							return;
						}
						else{
							Q.push(vecin);
							in_queue[vecin]=true;
							cnt_in_queue[vecin]++;
						}
					}
				}
			}
		}
	}
}	


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