#include <stdio.h>
#include <queue>
#include <vector>
#define MAX 50005
#define INF 1<<20
using namespace std;

typedef struct{
	int node, cost;
} TNod;

int n, m, i, j, x, y, z, d[MAX];
bool viz[MAX];
vector<TNod> L[MAX];
queue<int> q;

bool bf(int s);

int main(){
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	TNod aux;
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		aux.node = y;
		aux.cost = z;
		L[x].push_back(aux);
	}
	for(i = 1; i <= n; i++)
		q.push(i);
	if(bf(1) == false)
		printf("Ciclu negativ!\n");
	else{
		for(i = 2; i <= n; i++)
			printf("%d ", d[i] == INF ? 0 : d[i]);
		printf("\n");
	}
	return 0;
}

bool bf(int s){
	vector<TNod>::iterator it;
	for(i = 1; i <= n; i++)
		d[i] = INF;
	d[s] = 0;

	for(i = 0; i < n * m; i++){
		j = q.front();
		q.pop();
		viz[j] = true;
			
		it = L[j].begin();
		while(it < L[j].end()){
			if(d[it->node] > d[j] + it->cost){
				d[it->node] = d[j] + it->cost;
				if(viz[it->node] == true){
					viz[it->node] = false;
					q.push(it->node);
				}
			}
			it++;
		}
		if(q.empty())
			break;	
	}

	for(i = 2; i <= n; i++)
		while(!L[i].empty()){
			if(d[L[i].back().node] > d[i] + L[i].back().cost)
				return false;
			L[i].pop_back();
		}
	
	return true;
}