#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,D[NMAX];
char viz[NMAX];
vector<pair < int,int> >G[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(make_pair(y,c));
	}
}
void solve(){
	int x;
	for(int i=2;i<=N;i++)
		D[i]=INF;
	viz[1]=1;
	D[1]=0;
	Coada.push(1);
	contor=1;
	while(Coada.size()){
		x=Coada.front();
		for(int i=0;i<G[x].size();++i){
			if(D[G[x][i].first]>D[x]+G[x][i].second){
				D[G[x][i].first]=D[x]+G[x][i].second;
				if(!viz[G[x][i].first]){
					if(contor>N){
						g<<"Ciclu Negativ!";
						return;
					}
					else{
						viz[G[x][i].first]=1;
						contor++;
						Coada.push(G[x][i].first);
					}
				}
			}
		}
		Coada.pop();
	}
	for(int i=2;i<=N;++i)
		g<<D[i]<<" ";
}
int main (){
	read();
	solve();
	return 0;
}