#include <stdio.h>
#include <bitset>
#include <deque>
using namespace std;
FILE* f, * g;

int start[50002], t[4][500002], drum[50002], n, m, fr[50002], ok;
bitset <50002> viz;
deque <int>q;

void bellmanford()
{
    int no, nod, dr;
    q.push_back(1);
    viz[1] = 1;
    drum[1] = 0;
    while (!q.empty())
    {
        nod = q.front();
        viz[nod] = 0;///nu mai este in coada
        q.pop_front();
        no = start[nod];
        while (no)
        {
            dr = t[3][no];
            if (drum[t[0][no]] > dr + drum[nod])///am gasit o distanta mai buna de la nodul nod la nodul t[0][no]
            {
                drum[t[0][no]] = dr + drum[nod];
                ++fr[t[0][no]];
                if (fr[t[0][no]] > n)
                {
                    ok = 1;
                    break;
                }
                if (!viz[t[0][no]])///daca nu am mai introdus nodul t[0][no] in coada
                {
                    q.push_back(t[0][no]);
                    viz[t[0][no]] = 1;
                }
            }
            no = t[1][no];
        }
    }
}

void write()
{
    int i;
    if (!ok)
        for (i = 2;i <= n;++i)
            fprintf(g, "%d ", drum[i]);
    else
        fprintf(g, "Ciclu negativ!");
}

int main()
{
    int i, j, k = 0, o;
    f = fopen("bellmanford.in", "r");
    g = fopen("bellmanford.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (o = 1;o <= m;++o)
    {
        ++k;
        fscanf(f, "%d %d %d", &i, &j, &t[3][k]);
        t[0][k] = j, t[1][k] = start[i], start[i] = k;
    }
    for (i = 1;i <= n;++i) drum[i] = 2000000000;
    bellmanford();
    write();
    fclose(f);
    fclose(g);
    return 0;
}