#include <fstream>
#include <queue>
#include <vector>
#define nmax 100100
#define oo (1<<30)
#define vecin first
#define cost second
using namespace std;

vector < pair<int,int> > G[nmax];
queue <int> Q;
int N,Answer=1,nrinQ[nmax],Dist[nmax];
bool inQ[nmax];

void BellmanFord(int Start) {
	
	int i,Nod;
	
	Q.push(Start);
	Dist[Start]=0;
	
	while(!Q.empty()) {
		
		Nod=Q.front();
		inQ[Nod]=0;
		Q.pop();
		
		for(i=0;i<G[Nod].size();i++)
			if(Dist[Nod]+G[Nod][i].cost<Dist[G[Nod][i].vecin]) {
				
				Dist[G[Nod][i].vecin]=Dist[Nod]+G[Nod][i].cost;
				
				if(!inQ[G[Nod][i].vecin]) {
					
					Q.push(G[Nod][i].vecin);
					inQ[G[Nod][i].vecin]=1;
					nrinQ[G[Nod][i].vecin]++;
					
					if(nrinQ[G[Nod][i].vecin]>=N) {
						Answer=0;
						return;
						}
					
					}
			
				}
		
		}
	
}
void Solve() {
	
	for(int i=1;i<=N;i++)
		Dist[i]=oo;
	
	BellmanFord(1);
	
}
void Read() {
	
	int x,y,c,M;
	ifstream in("bellmanford.in");
	in>>N>>M;
	
	while(M--) {
		in>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
		}
	
	in.close();
	
}
void Write() {
	
	ofstream out("bellmanford.out");
	
	if(!Answer)
		out<<"Ciclu negativ!";
	else
		for(int i=2;i<=N;i++)
			out<<Dist[i]<<' ';
		
	out<<'\n';
	out.close();
	
}
int main() {
	
	Read();
	Solve();
	Write();
	
}