#include<bits/stdc++.h>
#include <fstream>
using namespace std;
#define maxn 50005
#define INF 1 << 30
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int N, M;
std::vector<pair<int, int>> v[maxn];
int cost[maxn];
//int verif[maxn];
int cnt[maxn];
queue<int> q;

void bell(int nod){
	for(int i = 1; i <= N; i++){
		cost[i] = INF;
	}
	cost[nod] = 0;
	//verif[nod] = 1;
	q.push(nod);
	while(!q.empty()){
		nod = q.front();
		//verif[a]=0;
		q.pop();
		cnt[nod]++;
		if(cnt[nod]==N){
		    fout<<"Ciclu negativ!";
            exit(0);
		}
		for(int i = 0; i < v[nod].size(); i++){
			int b = v[nod][i].first;
			int c = v[nod][i].second;
			if(cost[b] > cost[nod] + c){
				cost[b] = cost[nod] + c;
				q.push(b);
			}
		}
	}

}

int main(){
	fin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, val;
		fin >> x >> y >> val;
		v[x].push_back(make_pair(y, val));
	}
	bell(1);
	for(int i = 2; i <= N; i++){
		fout << cost[i]<<" ";
	}

	return 0;
}