#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define nmax 50005
#define INF 2000000000

struct drum
{
	int nod, cos;
} x, y;

vector<drum> G[nmax];
int N, M, cnt[nmax], cost[nmax], viz[nmax];

queue<int> Q;

void citire ()
{
	int a;
	scanf("%d %d",&N,&M);
	for (int i = 0; i < M; i++)
	{
		scanf ("%d %d %d",&a,&x.nod,&x.cos);
		G[a].push_back(x);
	}
}

void solve ()
{
	int i, vf;
	for (i = 1; i <= N; ++i) cost[i] = INF;
	cost[1] = 0; Q.push(1);
	while ( !Q.empty () )
	{
		vf = Q.front (); Q.pop ();
		viz[vf] = 0; cnt[vf]++;
		if (cnt[vf] > M) { printf("Ciclu negativ!\n"); return; }
		for (i = 0; i < G[vf].size (); ++i)
		{
			y = G[vf][i];
			if (cost[y.nod] > cost[vf] + y.cos)
			{
				cost[y.nod] = cost[vf] + y.cos;
				if ( !viz[y.nod] ) { viz[y.nod] = 1; Q.push(y.nod); }
			}
		}
	}
	for (i = 2; i <= N; ++i) printf("%d ", cost[i]);
}

int main ()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    citire();
    solve();
    return 0;
}