#include <fstream>
#include <list>
#include <limits>
using namespace std;

#define NMAX 50000
struct edge { int from, to, cost; };

int N, M;
list<edge> edges;
long long distances[NMAX+1];

void readInput() {
	int from, to, cost;
	ifstream f("bellmanford.in");
	f >> N >> M;
	for (int i=0;i<M;i++) {
		f >> from >> to >> cost;
		edge new_edge = {from, to, cost};
		edges.push_back(new_edge);
	}
	f.close();
}

bool bellman_ford(int s) {
	int i;
	for (i=1;i<=N;i++) {
		distances[i] = INT_MAX+1;
	}
	distances[s] = 0;
	for (i=1;i<N;i++) {
		for (list<edge>::iterator it = edges.begin();it!=edges.end();it++) {
			int to = ((edge)*it).to, from = ((edge)*it).from, cost = ((edge)*it).cost;
			if (distances[to] > distances[from]+cost) {
				distances[to] = distances[from]+cost;
			}
		}
	}
	for (list<edge>::iterator it = edges.begin();it!=edges.end();it++) {
		if (distances[((edge)*it).to] > distances[((edge)*it).from]+((edge)*it).cost) {
			return false;
		}
	}
	return true;
}

int main() {
	readInput();	
	ofstream g("bellmanford.out");
	if (bellman_ford(1)) {
		for (int i=2;i<=N;i++) {
			g<<distances[i]<<" ";
		}
		g<<"\n";
	}
	else {
		g << "Ciclu negativ!\n";
	}
	g.close();
	return 0;
}