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

using namespace std;

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

int cost[maxN], cont[maxN];
bool exist[maxN];
vector <pair <int, int> > list[maxN];
queue <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 a, b, c;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		list[a].PB ( MKP (b, c) );
	}
	
	for (int i = 2; i <= N; ++ i) cost[i] = inf;
	
	cont[1] = 1;
	exist[1] = true;
	Q.push (1);
	
	while (! Q.empty ())
	{
		int nod = Q.front();
		Q.pop();
		exist[nod] = false;
		
		for (unsigned int i = 0; i < list[nod].size(); ++ i)
		{
			int nod2 = list[nod][i].first;
			int cost2 = list[nod][i].second;
			
			if (cost[nod2] <= cost[nod] + cost2) continue;
			
			cont[nod2] ++;
			
			if (cont[nod2] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			cost[nod2] = cost[nod] + cost2;
			
			if (exist[nod2]) continue;
			
			Q.push (nod2);
			exist[nod2] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", cost[i]);
	
	return 0;
}