#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector <int> graph[100005];
vector <int> graphC[100005];
int viz[100005];
int dist[100005];

int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	int n, m;
	f >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		graphC[a].push_back(c);
	}
	for (int i = 2; i <= n; i++)
		dist[i] = 1000000;
	for (int i = 1; i <= n; i++)
	{
		viz[i]++;
		if (viz[i] == n-1)
		{
			g << "Ciclu negativ!";
			return 0;
		}
		int lim = graph[i].size();
		for (int j = 0; j < lim; j++)
		{
			int vecin = graph[i][j];
			int cost = graphC[i][j];
			viz[vecin]++;
			if (viz[vecin] == n-1)
			{
				g << "Ciclu negativ!";
				return 0;
			}
			if (dist[i] + cost < dist[vecin])
				dist[vecin] = dist[i] + cost;
		}
	}
	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";
	return 0;
}