#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#define inf 999999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int x,y,v,e;
vector <pair <int,int>> a[15001];
vector <int> predecesor;
vector <int> dist;


void Initializare(int s)
{
	int i;
	for(i=1; i<=v; i++)
		dist[i]=inf;
	dist[s]=0;
}


void Relax(int i,int j,int w)
{
	if(dist[j]>dist[i]+w)
	{
		dist[j]=dist[i]+w;
		predecesor[j]=i;
	}
}


bool BellmanFord(int s)
{
	int k,i,j,w;
	Initializare(s);
	for(k=1; k<v; k++)
	for(i=1; i<=v; i++)
	for(auto x:a[i])
	{
		j=x.first;
		w=x.second;
		Relax(i,j,w);
	}
	for (i=1; i<=v; i++)
	for(auto x:a[i])
	{
		j=x.first;
		w=x.second;
		if(dist[j]>dist[i]+w)
			return false;
	}
	return true;
}


int main()
{
	int s,w,i;
	f>>v>>e;
	while(f>>x>>y>>w)
		a[x].push_back({y,w});
	predecesor.resize(v+1);
	dist.resize(v+1);
	s=1;
	BellmanFord(s);
	if(BellmanFord(s)==true)
		for(i=1; i<=v; i++)
		{
			if(i!=s)
			{
			if(dist[i]==inf)
				g<<"INF"<<" ";
			else g<<dist[i]<<" ";
			}
		}
	else g<<"Ciclu negativ!";
	f.close();
	g.close();
	return 0;
}