#include <stdio.h>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
using namespace std;

#define N 50001

struct muchie
{
	int u;
	int v;
	int cost;

};

int d[N];
int p[N];

struct pereche {
	int v;
	int cost;
};

vector<pereche> *graf = new vector<pereche>[N];

vector<muchie> muchii;

int main()
{
	int i, j, u, v, c;
	int n, m;
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");

	f >> n >> m;

	for (i = 0; i < m; i++)
	{
		f >> u >> v >> c;
		muchie crt;
		crt.u = u;
		crt.cost = c;
		crt.v = v;

		pereche p;
		//p.v = u;
		//p.cost = c;


		//graf[v].push_back(p);

		p.v = v ;
		graf[u].push_back(p);

		muchii.push_back(crt);
	}

	int sursa = 1;
	for (i = 1; i <= n; i++)
		d[i] = INT_MAX / 3;
	d[sursa ] = 0;
	p[sursa] = 0;

	for (i = 0; i < graf[sursa].size(); i++)
		d[graf[sursa][i].v] = graf[sursa][i].cost;

	for (i = 1; i <= n - 2; i++)
	{
		for (j = 0; j < muchii.size(); j++)
		{
			if (d[muchii[j].v] > d[muchii[j].u] + muchii[j].cost)
			{
				d[muchii[j].v] = d[muchii[j].u] + muchii[j].cost;
				p[muchii[j].v] = muchii[j].u;
			}
		}
	}

	for (i = 0; i < muchii.size(); i++)
		if (d[muchii[i].v] > d[muchii[i].u] + muchii[i].cost)
		{	g << "Ciclu negativ!\n";
			return 0;
		}


	for (i = 2; i <= n; i++)
		if(d[i] < INT_MAX/3)
			g<<d[i]<<" ";
		else
			g<<"0 ";


}