#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, tata, urm, c;
	for (i = 1; i <= N; ++i) cost[i] = INF;
	cost[1] = 0;
	Q.push(1);
	while ( !Q.empty () )
	{
		tata = Q.front (); Q.pop ();
		viz[tata] = 0;
		cnt[tata]++;
		if ( cnt[tata] > M ) { printf("Ciclu negativ!"); return; }
		for (i = 0; i < G[tata].size (); ++i)
		{
			urm = G[tata][i].nod;
			c = G[tata][i].cos;
			if (cost[urm] > cost[tata] + c)
			{
				cost[urm] = cost[tata] + c;
				if ( !viz[urm] ) { viz[urm] = 1; Q.push(urm); }
			}
		}
	}
	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;
}