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

using namespace std;

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

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


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 ( MP (y, c) );
	}
	
	for (int i = 2; i <= N; ++ i) cost[i] = inf;
	
	Q.PB (1);
	cont2[1] ++;
	cont1[1] = true;
	
	
	for ( ; ! Q.empty (); )
	{
		int nod = Q.front();
		
		cont1[nod] = false;
		
		Q.PF ();
		
		for (unsigned int t = 0; t < lista[nod].size(); ++ t)
		{
			int nod2 = lista[nod][t].first;
			int val = lista[nod][t].second;
			
			if (cost[nod2] <= cost[nod] + val) continue;
			++ cont2[nod2];	
			
			if (cont2[nod2] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			cost[nod2] = cost[nod] + val;
			
			if (cont1[nod2]) continue;
			
			Q.PB (nod2);
			cont1[nod2] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", cost[i]);
	
	return 0;
}