#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int N=50001,INF=0x3f3f3f3f;

struct Nod{
	int x, c;
	Nod(int a, int b){
		x=a;
		c=b;
	}
};
vector<Nod> g[N];
int cost[N],nrq[N];
vector<int> q;
bool inq[N];
int n,m;
bool bf(int s){
	int x;
	for(int i=2 ; i<=n ; i++){
		cost[i]=0;
	}
	cost[1]=0;
	q.push_back(s);
	inq[s]=true;
	nrq[s]=1;
	size_t j=0;
	while(j<=q.size()){
		x=q[j++];
		inq[x]=false;
		for(size_t i=0 ; i<g[x].size() ; i++){
			if(cost[g[x][i].x]==0 || cost[g[x][i].x]>cost[x]+g[x][i].c){
				cost[g[x][i].x]=cost[x]+g[x][i].c;
				q.push_back(g[x][i].x);
				inq[g[x][i].x]=true;
				nrq[g[x][i].x]++;
				if(nrq[g[x][i].x]>n){
					return false;
				}
			}
		}
	}
	return true;
}
int main(){
	in>>n>>m;
	int x,y,c;
	for(int i=1 ; i<=m ; i++){
		in>>x>>y>>c;
		g[x].push_back(Nod(y,c));
	}
	if(bf(1)){
		for(int i=2 ; i<=n ; i++){
			out<<cost[i]<<' ';
		}
		out<<'\n';
	}else{
		out<<"Ciclu negativ!\n";
	}
	return 0;
}