// Dedicat lui DAVID G

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>

constexpr long long INF = LLONG_MAX / 4;
using node_t = int;
using weight_t = long long;
struct AdjNode {
	node_t node;
	weight_t weight;

	inline AdjNode() noexcept
		: node(), weight() {}

	inline AdjNode(node_t node, weight_t weight)
		: node(node), weight(weight) {}
};
using AdjList = std::vector<std::vector<AdjNode>>;
using DistanceMatrix = std::vector<std::vector<weight_t>>;

class Graph {
	size_t node_cnt;
	AdjList adj_list;

public:
	inline Graph(size_t node_cnt) noexcept
		: node_cnt(node_cnt), adj_list(node_cnt + 1, std::vector<AdjNode>()) {}

	inline Graph(size_t node_cnt, const AdjList& adj_list) noexcept
		: node_cnt(node_cnt), adj_list(adj_list) {}

	inline Graph(const Graph& graph) noexcept
		: node_cnt(graph.node_cnt), adj_list(graph.adj_list) {}

	inline Graph(Graph&& graph) noexcept {
		node_cnt = graph.node_cnt;
		graph.node_cnt = 0;
		adj_list = std::move(graph.adj_list);
	}

	inline Graph& operator =(const Graph& graph) noexcept {
		node_cnt = graph.node_cnt;
		adj_list = graph.adj_list;
		return *this;
	}

	inline Graph& operator =(Graph&& graph) noexcept {
		node_cnt = graph.node_cnt;
		graph.node_cnt = 0;
		adj_list = std::move(graph.adj_list);
	}

	inline size_t get_node_cnt() const noexcept {
		return node_cnt;
	}

	inline AdjList get_adj_list() const noexcept {
		return adj_list;
	}

	inline void add_edge(node_t node1, node_t node2, weight_t weight) noexcept {
		adj_list[node1].emplace_back(node2, weight);
	}

	inline void add_undirected_edge(node_t node1, node_t node2, weight_t weight) noexcept {
		adj_list[node2].emplace_back(node1, weight);
	}

	inline std::vector<weight_t> SPFA(node_t start_node, bool& negative_cycle) const noexcept {
		assert(1 <= start_node && start_node <= node_cnt);

		std::vector<int> in_queue(node_cnt + 1, false);
		std::vector<int> arcs(node_cnt + 1, 0);
		negative_cycle = false;

		std::vector<weight_t> distance(node_cnt + 1, INF);
		distance[start_node] = 0;

		std::queue<node_t> queue;
		queue.push(start_node);
		in_queue[start_node] = true;

		while (!queue.empty()) {
			node_t node = queue.front();
			queue.pop();
			in_queue[node] = false;

			for (const AdjNode& adj : adj_list[node])
				if (distance[node] + adj.weight < distance[adj.node]) {
					distance[adj.node] = distance[node] + adj.weight;
					if (!in_queue[adj.node]) {
						queue.push(adj.node);
						in_queue[adj.node] = true;
						arcs[adj.node] = arcs[node] + 1;
						if (arcs[adj.node] > node_cnt - 1)
							negative_cycle = true;
					}
				}
		}

		for (weight_t& dist : distance)
			if (dist == INF) dist = -1;

		return distance;
	}

	inline DistanceMatrix roy_floyd() const noexcept {
		DistanceMatrix distance(node_cnt + 1, std::vector<weight_t>(node_cnt + 1, INF));
		for (node_t node = 1; node <= node_cnt; ++node)
			distance[node][node] = 0;

		for (node_t node = 1; node <= node_cnt; ++node)
			for (const AdjNode& adj : adj_list[node])
				distance[node][adj.node] = adj.weight;

		for (node_t k = 1; k <= node_cnt; ++k)
			for (node_t i = 1; i <= node_cnt; ++i)
				for (node_t j = 1; j <= node_cnt; ++j)
					distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);

		for (node_t i = 1; i <= node_cnt; ++i)
			for (node_t j = 1; j <= node_cnt; ++j)
				if (distance[i][j] == INF) distance[i][j] = -1;

		return distance;
	}

	inline std::vector<weight_t> dijkstra(node_t start_node) const noexcept {
		assert(1 <= start_node && start_node <= node_cnt);

		std::vector<weight_t> distance(node_cnt + 1, INF);
		distance[start_node] = 0;

		std::vector<bool> processed(node_cnt + 1, false);
		std::priority_queue<std::pair<weight_t, node_t>> queue;
		queue.emplace(0, start_node);

		while (!queue.empty()) {
			node_t node = queue.top().second;
			queue.pop();
			if (processed[node]) continue;
			processed[node] = true;

			for (const AdjNode& adj : adj_list[node])
				if (distance[node] + adj.weight < distance[adj.node]) {
					distance[adj.node] = distance[node] + adj.weight;
					queue.emplace(-distance[adj.node], adj.node);
				}
		}

		for (weight_t& dist : distance)
			if (dist == INF) dist = -1;

		return distance;
	}
};

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

	node_t node1, node2, start_node;
	weight_t weight;
	int N, M, i, j;

	fin >> N >> M;

	Graph graph(N);
	for (i = 1; i <= M; ++i) {
		fin >> node1 >> node2 >> weight;
		graph.add_edge(node1, node2, weight);
	}

	bool negative_cycle;
	const auto distance = graph.SPFA(1, negative_cycle);

	if (negative_cycle) fout << "Ciclu negativ!";
	else {
		for (node1 = 2; node1 <= N; ++node1)
			fout << distance[node1] << ' ';
	}

	fin.close();
	fout.close();
	return 0;
}