#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();
        q.pop_front();
        viz[nod] = 0;///nu mai este in coada deoarece l-am eliminat
        ++fr[nod];///daca un nod a fost introdus de mai mult de n ori inseamna ca exista un ciclu negativ
        if (fr[nod] > n)
        {
            ok = 1;
            break;
        }
        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];
                if (!viz[t[0][no]])///daca nu exista 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;
}