#include <iostream>
#include <fstream>

#define Mm 250005
#define Nm 50004
#define INF (int)1e9+2;

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Graf
{
    int x, y, c;
};

Graf a[Mm];
int d[Nm];
int n, m;

void Solve()
{
    int i, j;
    for (i = 2; i <= n; ++i)
        d[i] = INF;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (d[a[j].y] > a[j].c + d[a[j].x])
                d[a[j].y] = a[j].c + d[a[j].x];
}

bool Negative()
{
    int i;
    for (i = 1; i <= m; i++)
        if (d[a[i].x] + a[i].c < d[a[i].y])
            return true;
    return false;
}

int main()
{
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> a[i].x >> a[i].y >> a[i].c;
    Solve();
    if (Negative())
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (i = 2; i <= n; i++)
        fout << d[i] << " ";
    return 0;
}