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

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

class edge
{
public:
	int cost;
	int nod;
};

queue<int> coada;
vector<int> dis;
vector<vector<edge> > graph;
int n,m;
int bel(int start)
{
	int i;
	dis[start]=0;
	int a;
	coada.push(start);
	int k=0;
	while(coada.size()>0)
	{
		a=coada.front();
		
		for(i=0;i<graph[a].size();i++)
		{
			if(dis[graph[a][i].nod]>dis[a]+graph[a][i].cost)
			{
				dis[graph[a][i].nod]=dis[a]+graph[a][i].cost;
				coada.push(graph[a][i].nod);
			}
		}
		coada.pop();
		if(k>=n)
			return -1;
		k++;
	}
	cout<<k;
	return 0;
}
int main()
{
	int i,x,y,z;
	edge aux;
	f>>n>>m;
	graph.resize(n+1);
	dis.resize(n+1,100000000);
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		aux.nod=y;
		aux.cost=z;
		graph[x].push_back(aux);
	}
	if(bel(1)==-1)
		{
			g<<"Ciclu negativ!";
		
	}
	else{
	for(i=2;i<=n;i++)
	if(dis[i]!=100000000)
		   g<<dis[i]<<" ";
	else g<<0<<" ";}
}