#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
#define N 50001
#define M 250001
#define inf 999999999
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x, y, cst, k;
int t[3][M], cost[N], start[N], nr[N];
bool viz[N], ciclu_neg;
queue <int> c;

void bellman_ford()
{
    int man, om;
    c.push(1);
    viz[1] = 1;
    while( !c.empty() && !ciclu_neg)
    {
        om = c.front();
        man = start[om];
        viz[om] = 0;
        while( man )
        {
            if(cost[om] + t[2][man] < cost[t[0][man]])
            {
                cost[t[0][man]] = cost[om] + t[2][man];
                if( !viz[t[0][man]])
                {
                    if(nr[t[0][man]] > n)
                        ciclu_neg = 1;
                    else
                    {
                        c.push(t[0][man]);
                        viz[t[0][man]] = 1;
                        nr[t[0][man]]++;
                    }
                }
            }
            man = t[1][man];
        }
        c.pop();
    }
}

int main()
{
    fin >> n >> m;
    while(fin >> x >> y >> cst)
    {
        k++;
        t[0][k] = y;
        t[1][k] = start[x];
        t[2][k] = cst;
        start[x] = k;
    }

    for(int i=2; i<=n; i++)
        cost[i] = inf;
    cost[1] = 0;

    bellman_ford();

    if( !ciclu_neg)
        for(int i=2; i<=n; i++)
            fout << cost[i] << " ";
    else
        fout << "Ciclu negativ!";
    return 0;
}