#include <fstream>
#include <vector>
#include <bitset>
#include <iostream>
#include <queue>
#include <climits>

using namespace std;

vector< vector<pair<int, int> > > citesteGraf(ifstream &in , int &n)
{
	vector< vector< pair<int, int> > > graf;
	pair<int, int> x;

	int m , m1 , m2 , cost;

	in >> n >> m;

	for (int i = 1; i <= n + 1; i++)
	{
		vector<pair<int, int>> y;
		graf.push_back(y);
	}

	for (int i = 0; i < m; i++)
	{
		in >> m1 >> m2 >> cost;
		x.first = m2;
		x.second = cost;

		graf[m1].push_back(x);
	}

	return graf;
}

vector<int> bellmanFort(vector<vector<pair<int, int>>> graf, int n)
{
	queue<int> coada;
	bitset<50001> v;
	vector<int> sol(n + 1, INT_MAX) , ver(n + 1 ,  0);
	int nod;
	bool cicluNegativ = false;

	coada.push(1);
	sol[1] = 0;

	while (coada.empty() != true && cicluNegativ == false)
	{
		nod = coada.front();
		coada.pop();
		v[nod].flip();

		for (vector < pair<int, int>>::iterator it = graf[nod].begin(); it != graf[nod].end(); it++)
		{
			if (sol[nod] < INT_MAX)
			{
				if (sol[it->first] > sol[nod] + it->second)
				{
					sol[it->first] = sol[nod] + it->second;
					if (v[it->first] == 0)
					{
						if (ver[it->first] <= n)
						{
							v[it->first].flip();
							coada.push(it->first);
							ver[it->first]++;
						}
						else
						{
							cicluNegativ = true;
						}
					}
				}
			}
		}
	}
	if (cicluNegativ == true)
	{
		sol[0] = -123;
	}
	else
	{
		sol[0] = 123;
	}
	return sol;
}

int main()
{
	ifstream in("bellmanford.in");
	ofstream out("bellmanford.out");
	vector <vector<pair<int, int>> > g;
	int n;

	g = citesteGraf(in, n);

	vector<int> sol = bellmanFort(g, n);

	if (sol[0] == 123)
	for (int i = 2; i <= n; i++)
	{
		out << sol[i] << ' ';
	}
	else
	{
		out << "Ciclu negativ!\n";
	}
	out << endl;

	in.close();
	out.close();
	return 0;
}