#include<fstream>
#include<vector>
#include<cstring>

#define Nmax 50010
#define nrmax 1000000
#define INFI 0x3f3f3f3f

using namespace std;

int i, n, m, x, y, z, viz[Nmax], start, stop, nr, bun[Nmax], j, lung, nc;
struct cost
{
    int nod;
    int c;
};

vector <cost> muchie[Nmax];
vector <int> coada;

int sol ()
{
    for (i = 1; i <= n; ++i)
    {
        lung = muchie[i].size();
        for (j = 0; j < lung; ++j)
        {
            if (bun[i] + muchie[i][j].c < bun[muchie[i][j].nod])
                return 1;
        }
        return 0;
    }
}

int main()
{
    ifstream f("bellmanford.in");
    ofstream h("bellmanford.out");
    f >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        f >> x >> y >> z;
        muchie[x].push_back(cost{y, z});
    }
    f.close();
    memset (bun, INFI, sizeof(bun));
    start = stop = 0;
    coada.push_back(1);
    nr = 0;
    bun[1] = 0;
    viz[1] = 1;
    while (start <= stop)
    {
        nc = coada[start];
        viz[nc] = 0;
        lung = muchie[nc].size();
        for (i = 0; i < lung; ++i)
        {
            if (bun[muchie[nc][i].nod] > bun[nc] + muchie[nc][i].c)
            {
                bun[muchie[nc][i].nod] = bun[nc] + muchie[nc][i].c;
                if (viz[muchie[nc][i].nod] == 0)
                {
                    coada.push_back(muchie[nc][i].nod);
                    viz[muchie[nc][i].nod] = 1;
                    ++stop;
                }
            }
            ++nr;
        }
        ++start;
        if (nr > nrmax)
            break;
    }
    if (sol())
        h << "Ciclu negativ!\n";
    else
        for (i = 2; i <= n; ++i)
            h << bun[i] << " ";
    h.close();
    return 0;
}