#include <fstream>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int a[3][250005], start[50005], c[250005], viz[50005], coada[500005], fr[50005], n, m;
bool ok = true;
void ford();
void afisare();
int main()
{
    int x, i;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> a[0][i] >> a[2][i];
        a[1][i] = start[x];
        start[x] = i;
    }
    coada[1] = 1;
    for (i = 2; i <= n; i++)
        c[i] = 100000000;
    ford();
    afisare();
    fin.close();
    fout.close();
    return 0;
}
void ford()
{
    int ps = 1, pi = 1, x, p;
    while (ps <= pi) {
        x = coada[ps];
        viz[x] = 0;
        p = start[x];
        while (p) {
            if (c[x] + a[2][p] < c[a[0][p]]) {
                c[a[0][p]] = c[x] + a[2][p];
                if (c[1] < 0) {
                    ok = false;
                    return;
                }
                if (!viz[a[0][p]]) {
                    viz[a[0][p]] = 1;
                    pi++;
                    coada[pi] = a[0][p];
                    fr[a[0][p]]++;
                    if (fr[a[0][p]] > m) {
                        ok = false;
                        return;
                    }
                }
            }
            p = a[1][p];
        }
        ps++;
    }
}
void afisare()
{
    if (ok == false)
        fout << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++) {
            if (c[i] == 100000000)
                c[i] = 0;
            fout << c[i] << " ";
        }
}