#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 999999999

using namespace std;



ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");



vector <pair<int, int>> v[50050];

queue<int> q;



int n, m, a, b, c, freq[50050], cost[50050];



int main()

{

	fin >> n >> m;

	for (int i = 0; i < m; i++)

	{

		fin >> a >> b >> c;

		v[a].push_back(make_pair(b, c));



	}



	//init costuri:

	for (int i = 2; i <= n; i++)

		cost[i] = inf;

	cost[1] = 0;

	q.push(1);

	while (!q.empty())

	{

		int aux = q.front();

		freq[aux]++;

		if (freq[aux] >= m)

		{

			fout << "Ciclu negativ!";

			return 0;

		}

		q.pop();

		for (unsigned int i = 0; i < v[aux].size(); i++)

		{

			pair<int, int> x = v[aux][i];

			if (cost[x.first] > cost[aux] + x.second)

			{

				cost[x.first] = cost[aux] + x.second;

				q.push(x.first);

			}

		}

	}



	for (int i = 2; i <= n; i++)

		fout << cost[i] << " ";

	return 0;

}