#include<fstream>
#include<vector>
#include<queue>
#define NMAX 250008
#define INF 4000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int N,M,contor[NMAX],D[NMAX],c;
char viz[NMAX];
vector<int >G[NMAX],C[NMAX];
queue<int>Coada;
void read (){
	f>>N>>M;
	int x,y,c;
	for(int i=1;i<=M;i++){
		f>>x>>y>>c;
		G[x].push_back(y);
		C[x].push_back(c);
	}
}
void solve(){
	int x;
	for(int i=2;i<=N;i++)
		D[i]=INF;
	viz[1]=1;
	D[1]=0;
	Coada.push(1);
	int ok=1;
	while( ok &&Coada.size()){
		
		x=Coada.front();
		
		viz[x]=0;
		
		for(int i=0;i<G[x].size();++i){
			
			if(D[G[x][i]]>D[x]+C[x][i]){
				
				D[G[x][i]]=D[x]+C[x][i];
				
				if(!viz[G[x][i]]){
					
					if(contor[G[x][i]]>N){
						
						g<<"Ciclu negativ!";
						
						return;
					}
					else{
						viz[G[x][i]]=1;
						
						++contor[G[x][i]];
						
						Coada.push(G[x][i]);
						
					}
				}
			}
		}
		
		Coada.pop();
	}
	
	for(int i=2;i<=N;++i)
		g<<D[i]<<" ";
}
int main (){
	read();
	
	solve();
	
	return 0;
	
}