#include<iostream>
#include<algorithm>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct edge{
	int dest,cost;
};

struct node{
	int value,dist;
};

const int mx= 50001;
const int inf= 1e9;

int n,m;
vector<edge> g[mx];
vector<int> cost;



void read(){
	in>>n>>m;
	int a,b,c;

	for(int i=0;i<m;i++){
		in>>a>>b>>c;
		g[a].push_back({b,c});
	}

	cost.resize(n+1,inf);
}

void solve(){
	queue<node> q;

	cost[1]=0;
	q.push({1,0});

	while(!q.empty()){
		node here=q.front();
		q.pop();
		for(edge e: g[here.value]){
			int new_cost = cost[here.value]+e.cost;
			if(new_cost<cost[e.dest]){

				int new_dist = here.dist+1;
				if(new_dist == n){
					out<<"Ciclu negativ!";
					return;
				}

				cost[e.dest]=new_cost;
				q.push({e.dest,new_dist});

			}
		}
	}
	for(int i=2;i<=n;i++){
		out<<cost[i]<<" ";
	}

}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	read();
	solve();

	return 0;
}