#include <vector>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct art {
	int nod;
	int cost;
};
struct art2 {
	int parinte;
	int cost;
};
vector<art2> D;
vector< vector<art> > G;
int main() {
	int n, m,x,y,c;
	int w = 1;
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		f >> x >> y >> c;
		art aux;
		aux.nod = y;
		aux.cost = c;
		G[x].push_back(aux);
	}
	D.push_back(art2{ 0,0 });
	for (int i = 1; i <= n; i++) {
		art2 aux;
		aux.cost = 10000;
		aux.parinte = -1;
		D.push_back(aux);
	}
	art2 aux;
	aux.cost = 0;
	aux.parinte = 0;
	D[1] = aux;
	for (int i = 1; i < n; i++) {
		for(int j=0;j<G.size();j++)
			for (int k=0;k<G[j].size();k++)
			{
				if (D[G[j][k].nod].cost > D[j].cost + G[j][k].cost)
				{
					D[G[j][k].nod].cost = D[j].cost + G[j][k].cost;
					D[G[j][k].nod].parinte = j;
				}
			}
	}
	for (int j = 0; j<G.size(); j++)
		for (int k = 0; k<G[j].size(); k++)
		{
			if (D[G[j][k].nod].cost > D[j].cost + G[j][k].cost)
			{
				w = 0;
			}
		}
	if (w == 0) g << "Ciclu negativ!";
	else {
		for (int i = 2; i <= n; i++)
			g << D[i].cost << ' ';
	}
}