/*
          ~Keep It Simple!~
*/

#include<stdio.h>
#include<list>

#define NMax 50005
#define inf 1000000000

using namespace std;

int N,M,n;

list< pair<int,int> > G[NMax];
int Dist[NMax],Heap[NMax],Poz[NMax];
bool viz[NMax];

void GoDown(int node)
{
	int aux, x = 0;

	while( x!=node )
	{
		 x = node;

		 if( x*2 <= n && Dist[Heap[node]]>Dist[Heap[x*2]] ) node = x*2;
		 if( x*2+1 <=n && Dist[Heap[node]]>Dist[Heap[x*2+1]] ) node = x*2+1;
 
		 aux = Heap[x];
		 Heap[x] = Heap[node];
		 Heap[node] = aux;

		 Poz[Heap[x]] = x;
		 Poz[Heap[node]] = node;

	}
}

void RemoveFromHeap()
{
	Poz[Heap[1]] = -1;
	Heap[1] = Heap[n--];
	Poz[Heap[1]] = 1;

	GoDown(1);
}

void Update( int node )
{
	int aux;
	while(node/2 && Dist[Heap[node/2]] > Dist[Heap[node]])
	{
		aux = Heap[node];
		Heap[node] = Heap[node/2];
		Heap[node/2] = aux;

		Poz[Heap[node]] = node;
		Poz[Heap[node/2]] = node/2;

		node/=2;
	}
}

void Insert(int node)
{
	Heap[++n] = node;
	Poz[node] = n;

	Update(n);
}

void BellManFord()
{
	for(int i=2; i<=N; i++)
	{
	  Dist[i] = inf;
	  Heap[i] = Poz[i] = i;
	}
	Heap[1] = Poz[1] = 1;
	int Source;
	Insert(1);
	while ( n )
	{
		Source = Heap[1];
		RemoveFromHeap();
		viz[Source] = 1;
		for(list< pair<int,int> >::iterator it = G[Source].begin(); it!=G[Source].end(); it++)
		{
			if(Dist[Source]+it->second < Dist[it->first])
			{
				Dist[it->first] = Dist[Source] + it->second;
				if( !viz[it->first] )
				{
					viz[it->first] =1;
				    Insert(it->first);
				}
			}
		}
	}
}


int Ciclu_Negativ()
{
	for(int i=1; i<=N; i++)
		for(list<pair<int,int>>::iterator it = G[i].begin(); it!=G[i].end(); it++)
			if( Dist[i] + it->second < Dist[it->first] )
				return 1;
	return 0;
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);

	scanf("%d%d",&N,&M);

	int x,y,c;

	for(int i=1; i<=M; i++)
	{
		scanf("%d%d%d",&x,&y,&c);

		G[x].push_back(make_pair(y,c));
	}

	BellManFord();

	if( Ciclu_Negativ() )
	{
		printf("Ciclu negativ!");
	}
	else
	{
	for(int i=2; i<=N; i++)
		printf("%d ",Dist[i]);
	}
}