#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;


#define maxN 50005
#define INF 0x3f3f3f3f
#define PB push_back
#define MKP make_pair


int N , M , cost[maxN] , node_count[maxN];
bool inQ[maxN];

vector <pair <int , int> > lista[maxN];
queue <int> Q;

int main ()
{
	freopen ("bellmanford.in" , "r" , stdin);
	freopen ("bellmanford.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		lista[a].PB (MKP (b , c));
	}
	
	
	for (int i = 2 ; i <= N ; ++i)
		cost[i] = INF;
	
	
	Q.push (1);
	
	inQ[1] = true;
	node_count[1] = 1;
	
	
	while (!Q.empty ())
	{
		int nod = Q.front ();
		
		Q.pop ();
		inQ[nod] = false;
		
		
		for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
		{
			int nodcur = lista[nod][i].first;
			int costcur = lista[nod][i].second;
			
			if (cost[nodcur] <= cost[nod] + costcur) continue;
			
			cost[nodcur] = cost[nod] + costcur;
			++node_count[nodcur];
			
			
			if (node_count[nodcur] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			
			if (!inQ[nodcur])
			{
				Q.push (nodcur);
				inQ[nodcur] = true;
			}
		}
	}
	
	
	for (int i = 2 ; i <= N ; ++i)
		if (cost[i] == INF)
			printf ("0 ");
		
		else printf ("%d " , cost[i]);
	
	
	
	return 0;
}