#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>

using namespace std;

#define maxN 50005
#define inf (1 << 30)
#define PB push_back
#define PF pop_front
#define MKP make_pair

deque <int> Q;
bool cont1[maxN];
int cont2[maxN];
vector < pair <int, int> > lista[maxN];
int cost[maxN];


int main ()
{
	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N ,&M);
	
	while (M --)
	{
		int x, y, c;
		
		scanf ("%d %d %d", &x, &y, &c);
		
		lista[x].PB ( MKP (y, c) );
	}
	
	
	for (int i = 2; i <= N; ++ i) cost[i] = inf;
	
	cost[1] = 0;
	cont1[1] = true;
	cont2[1] = 1;
	
	Q.PB (1);
	
	for ( ; ! Q.empty (); )
	{
		int nod = Q.front();
		
		cont1[1] = false;
		
		Q.PF();
		
		for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		{
			int node = lista[nod][i].first;
			int value = lista[nod][i].second;
			
			if (cost[node] < cost[nod] + value) continue;
			
			++ cont2[node];
			
			if (cont2[node] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			cost[node] = cost[nod] + value;
			
			
			if (cont1[nod]) continue;
			
			Q.PB (node);
			cont1[node] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", cost[i]);
	
	return 0;
}