#include <stdio.h>
#include <vector>
#include <deque>
#define nmax 50001
#define inf 0x3f3f

using namespace std;

struct drum
{
	int nod, cos;
}x;

vector <drum> V[nmax];
deque <int> Q;
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 ()
{
	for (int i = 1; i <= n; i++)
		cost[i] = inf;
	cost[1] = 0;
	Q.push_back (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_front();
		viz[top]=0;
        for (int i = 0; i < V[top].size(); i++)
            if (cost[V[top][i].nod] > c + V[top][i].cos)
            {
                cost[V[top][i].nod] = c + V[top][i].cos;
                if (!viz[V[top][i].nod])
                {
                    viz[V[top][i].nod] = 1;
                    Q.push_back(V[top][i].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;
}