#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

const int MAX_N = 50001;
const int MAX_M = 250001;

typedef std::pair<int, int> edge;


int n, m;
std::vector<edge> graph[MAX_N];
std::queue<edge> queue;
int cost[MAX_N];
int walks[MAX_N];
bool cycle = false;

void read()
{
	std::ifstream input("bellmanford.in");
	input >> n >> m;
	int x, y, w;
	for (int edge(0); edge < m; ++edge) {
		input >> x >> y >> w;
		graph[x].push_back(std::make_pair(w, y));
	}
	input.close();
}

void print()
{
	std::ofstream output("bellmanford.out");
	if (!cycle) {
		for (int vertex(2); vertex <= n; ++vertex) {
			output << cost[vertex] << ' ';
		}
	} else {
		output << "Ciclu negativ!";
	}
	output.put('\n');
	output.close();
}

void bellmanford()
{
	cost[1] = 0;
	walks[1] = 1;
	for (int vertex(2); vertex <= n; ++vertex) {
		cost[vertex] = std::numeric_limits<int>::max();
	}
	queue.emplace(0, 1);
	int new_cost;
	while (!queue.empty()) {
		auto connection = queue.front();
		queue.pop();
		if (connection.first > cost[connection.second]) {
			continue;
		}
		for (auto it : graph[connection.second]) {
			new_cost = cost[connection.second] + it.first;
			if (new_cost < cost[it.second]) {
				++walks[it.second];
				if (walks[it.second] == n) {
					cycle = true;
					return;
				}
				cost[it.second] = new_cost;
				queue.emplace(new_cost, it.second);
			}
		}
	}
}

int main()
{
	read();
	bellmanford();
	print();
	return 0;
}