#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <set>

using namespace std;
const int MAX = 1<<28;


vector<int> ford(vector<vector<pair<int,int> > > &V)
{
	int N = V.size();
	vector<int> D(N,MAX);
	bool relaxed = false;
	bool neg_cycle = false;
	D.at(0) = 0;
	set<int> S;
	for(int i=0;i<N;i++)
		S.insert(i);

	for(int i=0; i<N;i++)
	{	
		if(S.count(i) == 0)
			continue;
		relaxed = false;
		for(int j=0; j<N; j++)
			for(int k = 0; k<V.at(j).size(); k++)
			{
				int p = D.at(j) + V.at(j).at(k).second;
				int curr = D.at(V.at(j).at(k).first); 
				if(p < curr)
				{
					D.at(V.at(j).at(k).first) = p;
					relaxed = true;
					S.insert(V.at(i).at(k).first);
				}
			}
		if(!relaxed)
			S.erase(i);
		if(i==N-1 && relaxed == true)
			neg_cycle = true;		
	}
	if(neg_cycle)
		D.at(0) = -1;
	return D;
}


int main()
{
	ifstream fin("bellmanford.in");
	int N,M;
	fin>>N>>M;
	vector<vector<pair<int,int> > > V(N);
	
	for(int i=0; i<M; i++)
	{	
		int from, to, val;
		fin>>from>>to>>val;
		from--;
		to--;
		V.at(from).push_back(make_pair(to,val));
	}

	vector<int> D = ford(V);
	ofstream fout("bellmanford.out");
	if(D.at(0) == -1)
		fout<<"Ciclu negativ!";
	else
		for(int i=1; i<D.size(); i++)
			fout<<D.at(i)<<" ";

	fin.close();
	fout.close();
	return 0;
}