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

using namespace std;

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

int cost[maxN], cont[maxN];
bool exist[maxN];
vector < pair <int, int> > lista[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 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;
	
	Q.push (1);
	exist[1] = true;
	cont[1] = 1;
	
	while (! Q.empty ())
	{
		int nod = Q.front();
			
		Q.pop();
		exist[nod] = false;
		
		for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		{
			int node = lista[nod][i].first;
			int cost_node = lista[nod][i].second;
			
			if (cost[node] <= cost_node + cost[nod]) continue;
			
			++ cont[node];
			
			if (cont[node] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			cost[node] = cost_node + cost[nod];
			
			if (exist[node]) continue;
			
			Q.push (node);
			exist[node] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", cost[i]);
	
	return 0;
}