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


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;
	vector<int> M(N);
	for(int i=0;i<N;i++)
		M[i] = i;

	for(int i=0; i<M.size();i++)
	{
		vector<int> tmp;
		
		relaxed = false;
		for(int j=0; j<N; j++)
		{
			int size = V[j].size();
			for(int k = 0; k<size; k++)
			{
				int node_id = V[j][k].first;
				int p = D[j] + V[j][k].second;
				int curr = D[node_id]; 
				if(p < curr)
				{
					D[node_id] = p;
					relaxed = true;
					tmp.push_back(node_id);
				}
			}
		}
		M = tmp;
		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;
}