#include <iostream>
#include <fstream>
#include <stdint.h>

const int32_t MAX_N = 50000;
const int32_t MAX_M = 250000;
const int32_t MAX_COST = 50000000;

struct Queue {
	int32_t start = 0, end = 0;
	int32_t queue[MAX_N + 1];
	bool nodesInQueue[MAX_N];

	void Push(int32_t node) {
		if(nodesInQueue[node])
			return;
		
		nodesInQueue[node] = true;
		queue[end] = node;
		++end;
		if(end == MAX_N + 1)
			end = 0;
	}
	int32_t Pop() {
		int32_t node = queue[start];
		nodesInQueue[node] = false;
		++start;
		if(start == MAX_N + 1)
			start = 0;
		return node;
	}
	bool IsEmpty() {
		return start == end;
	}
};

struct Node {
	int32_t adjStart;
	int32_t cost;
	int32_t relaxCount;
};
struct AdjItem {
	int32_t node;
	int32_t cost;
	int32_t next;
};

int32_t n, m;
Node nodes[MAX_N];
AdjItem adj[MAX_M];
Queue queue;

void ReadGraph(std::istream& fin) {
	fin >> n >> m;

	for(int32_t i = 0; i != n; ++i) {
		nodes[i].adjStart = -1;
		nodes[i].cost = MAX_COST;
	}
	for(int32_t i = 0; i != m; ++i) {
		int32_t node1, node2, cost;
		fin >> node1 >> node2 >> cost;
		--node1; --node2;

		adj[i].node = node2;
		adj[i].cost = cost;
		adj[i].next = nodes[node1].adjStart;
		nodes[node1].adjStart = i;
	}
}
bool SetNodeDists() {
	nodes[0].cost = 0;
	queue.Push(0);

	while(!queue.IsEmpty()) {
		int32_t node = queue.Pop();

		for(int32_t ind = nodes[node].adjStart; ind != -1; ind = adj[ind].next) {
			int32_t next = adj[ind].node;
			int32_t nextCost = nodes[node].cost + adj[ind].cost;
			if(nodes[next].cost <= nextCost)
				continue;
			
			nodes[next].cost = nextCost;
			queue.Push(next);
		}

		++nodes[node].relaxCount;
		if(nodes[node].relaxCount == n)
			return false;
	}

	return true;
}
void OutputRes(std::ostream& fout) {
	for(int32_t i = 1; i != n; ++i)
		fout << nodes[i].cost << ' ';
	fout << '\n';
}

int main() {
	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");

	ReadGraph(fin);

	if(SetNodeDists()) {
		OutputRes(fout);
	} else {
		fout << "Ciclu negativ!\n";
	}

	fin.close();
	fout.close();

	return 0;
}