#include <stdio.h>
#include <vector>
#include <queue>
#define nmax 50005
#define inf 2000000000

using namespace std;

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

vector <drum> V[nmax];
int n, m, cnt[nmax], cost[nmax], viz[nmax];

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);
		V[a].push_back(x);
	}
}

void solve ()
{
	queue <int> Q;
	for (int i = 1; i <= n; i++)
		cost[i] = inf;
	cost[1] = 0;
	Q.push(1);
	int top, c;
	while ( !Q.empty() )
	{
		top = Q.front();
		c = cost[top];
		cnt[top]++;
		if (cnt[top]>=m)
		{
			printf("Ciclu negativ!\n");
			return;
		}
		Q.pop ();
		viz[top]=0;
        for (int i = 0; i < V[top].size(); i++)
		{
			y = V[top][i];
            if (cost[y.nod] > c + y.cos)
            {
                cost[y.nod] = c + y.cos;
                if (!viz[y.nod])
                {
                    viz[y.nod] = 1;
                    Q.push(y.nod);
                }
            }
		}
	}
    for (int 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;
}