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

using namespace std;

#define maxN 50010
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define NODE first
#define COST second

int Cost[maxN], Cont[maxN];
bool Viz[maxN];
vector <pair <int, int> > G[maxN];
vector <pair <int, int> > :: iterator it;
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);
		
		G[x].PB ( MKP (y, c) );
	}
	
	for (int i = 2; i <= N; ++ i) Cost[i] = inf;
	
	Q.push (1);
	Viz[1] = 1;
	Cont[1] = 1;
	
	while (! Q.empty ())
	{
		int nod = Q.front();
		Q.pop();
		Viz[nod] = false;
		
		for (it = G[nod].begin(); it != G[nod].end(); ++ it)
		{
			int nod2 = it -> NODE, cost2 = it -> COST;
			
			if (Cost[nod2] <= Cost[nod] + cost2) continue;
			
			Cost[nod2] = Cost[nod] + cost2;
			++ Cont[nod2];
			
			if (Cont[nod2] > N)
			{
				printf ("Ciclu negativ!");
				return 0;
			}
			
			if (Viz[nod2]) continue;
			Q.push (nod2);
			Viz[nod2] = true;
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", Cost[i]);
	
	return 0;
}