#include <iostream>
#include <fstream>
using namespace std;

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

#define NMAX 50001

struct graph{
	int nod, cost;
	graph *next;
};
graph *v[NMAX];

void add(int i, int j, int k) {
	graph *p = new graph;
	p->nod = j;
	p->cost = k;
	p->next = v[i];
	v[i] = p;
}

struct queue{
	int item;
	queue *next;
};
queue *front;
queue *coada = new queue;
bool first = false;

void insert(int x) {
	queue *p = new queue;
	p->item = x;
	coada->next = p;
	coada = p;
	coada->next = NULL;
	if (!first) front = coada, first = true;
}

void erase() {
	queue *p = new queue;
	p = front;
	front = front->next;
	p = NULL;
	delete p;
}

int N, M;
int a, b, c;

int dist[NMAX];
int ord[NMAX];

int BellmanFord() {
	int x;
	insert(1);
	while (front) {
		x = front->item;
		for (graph *it = v[x]; it; it = it->next) {
			if (dist[x] + (it->cost) < dist[it->nod]) {
				dist[it->nod] = dist[x] + (it->cost);
				insert(it->nod);
				ord[it->nod] = ord[x] + 1;
				if (ord[it->nod] > N) 
					return 0;
			}
		}
		erase();
	}
	return 1;
}

int main() {
	fin >> N >> M;
	while (M--) {
		fin >> a >> b >> c;
		add(a, b, c);
	}
	for (int i = 2; i <= N; ++i) dist[i] = 0x3f3f3f3f;
	if (BellmanFord()) {
		for (int i = 2; i <= N; ++i) fout << dist[i] << ' ';
		fout << '\n';
	}
	else 
		fout << "Ciclu negativ!\n";
	return 0;
}