#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
#define INF 0x3f3f3f3f;
using namespace std;

const int LIM = 50005;

vector <pair<int, int>> GRAF[LIM];
queue <int> coada;
int n, m, eincoada[LIM];
int viz[LIM], d[LIM];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


bool bellmanford(int sursa)
{
	for (int i = 1; i <= n; i++)
	{
		viz[i] = 0;
		eincoada[i] = 0;
		d[i] = INF;

	}
	d[sursa] = 0;
	coada.push(sursa);
	eincoada[sursa] = 1;
	while (!coada.empty())
	{
		int nodCurent = coada.front();
		viz[nodCurent]++;
		if (viz[nodCurent] >= n)
			return false;
		coada.pop();
		eincoada[nodCurent] = 0;

			for (size_t i = 0; i < GRAF[nodCurent].size(); i++)
			{
				int vecin = GRAF[nodCurent][i].first;
				int cost = GRAF[nodCurent][i].second;
				if (d[nodCurent] + cost < d[vecin])
				{
					d[vecin] = d[nodCurent] + cost;
					if (!eincoada[vecin])
						coada.push(vecin);
				}
		    }
				
	}
	return true;

}

int main()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		GRAF[x].push_back(make_pair(y, c));

	}
	if (bellmanford(1))
	{
		for (int i = 2; i <= n; i++)
			g << d[i] << " ";
	}
	else
		g << "Ciclu negativ!";

	return 0;


}