#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
std::ifstream f("bellmanford.in");
//std::ifstream f("input.txt");
std::ofstream o("bellmanford.out");

std::vector<int>g[50005];
std::map<std::pair<int, int>, int>costs;
int nodes, edges;
std::vector<int>distances(50005, INT_MAX);
std::vector<int>visited(50005, 0);
bool cycle = false;

int bellman_ford(int start)
{
	distances[start] = 0;
	for (size_t node = 1; node < nodes; node++)
	{
		for (std::vector<int>::iterator n = g[node].begin(); n < g[node].end(); n++)
		{
			if (distances[node] + costs[std::make_pair(node, *n)] < distances[*n])
			{
				distances[*n] = distances[node] + costs[std::make_pair(node, *n)];
			}
		}
	}

	for (size_t node = 1; node < nodes; node++)
	{
		for (auto& edge : costs)
		{
			if (distances[edge.first.first] + edge.second < distances[edge.first.second])
			{
				//distances[edge.first.first] + edge.second < distances[edge.first.second]
				cycle = true;
				return 0;
			}
		}
	}


}

int main()
{
	f >> nodes >> edges;
	int i = edges;
	while (i--)
	{

		int start, to, cost;
		f >> start >> to >> cost;
		g[start].push_back(to);
		costs[std::make_pair(start, to)] = cost;
	}

	int ans = bellman_ford(1);

	if (cycle == true)
	{
		//std::cout << "Ciclu negativ!";
		o << "Ciclu negativ!";
	}
	else {
		for (size_t i = 2; i <= nodes; i++)
		{
			//std::cout << distances[i] << " ";
			o << distances[i] << " ";
		}
	}
	return 0;
}