#include<iostream>
#include<vector>
#include<queue>
#include<fstream>
#define inf 0x3f3f3f3f
#define NMAX 50010
#define MMAX NMAX*5
using namespace std;
bool inQ[NMAX];
vector<pair<int, int>> g[NMAX];
queue<int> coada;
int d[NMAX];
int viz[NMAX];
int n, m;

ifstream f("bellmanford.in");
ofstream gg("bellmanford.out");


void cit()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		g[x].push_back({ y,c });
	}
}


bool bellmanford(int src)
{
	for (int i = 1; i <= n; i++)
		d[i] = inf,viz[i]=0;
	d[src] = 0;
	viz[src]++;
	coada.push(src);
	inQ[src] = true;
	while (!coada.empty())
	{
		int extract = coada.front();
		viz[extract]++;
		coada.pop();
		inQ[extract] = false;
		if (viz[extract] >= n)
			return false;
		for (auto& it : g[extract])
		{
			int vec = it.first;
			int cost = it.second;
			if (d[extract] + cost < d[vec])
			{
				d[vec] = d[extract] + cost;
				if (!inQ[vec])
				{
					coada.push(vec);

				}
			}
		}


	}
	return true;
}


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