#include <stdio.h>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <cstdlib>
#include <queue>
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;
bool *imbunatatit = new bool[N];
int *vizite = (int*)calloc(N, sizeof(int));

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 ;
		p.cost = c;
		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; i++)
		imbunatatit[i] = false;

	queue<int> q;
	q.push(1);
	imbunatatit[1] = true;

	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		imbunatatit[u] = false;

		for (j = 0; j < graf[u].size(); j++)
		{
			int v = graf[u][j].v;
			if (d[u] < INT_MAX / 3)
			{
				if ( d[v] > d[u] + graf[u][j].cost)
				{
					d[v] = d[u] + graf[u][j].cost;
					if (!imbunatatit[v])
					{
						if (vizite[v] > n)
						{
							cout << "Ciclu negativ\n";
							return 0;
						}
						q.push(v);
						imbunatatit[v] = true;
						vizite[v] ++;

					}
				}
			}
		}


	}

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