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

#define NMAX 50005
#define oo 0x3f3f3f3f

using namespace std;

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

int dist[NMAX], i, n, m, x, y, cost;
bool ok=true;
vector < pair<int, int> > G[NMAX];

void belFrd(int nodInit)
{
    for (i=nodInit; i<=n; i++)
    {
        int nodCurent = i;
        int nrvecini = G[i].size();
        for (int j=0; j<nrvecini; j++)
        {
            int vecin = G[i][j].first;
            int costVecin = G[i][j].second;

            if (dist[nodCurent] + costVecin < dist[vecin])
                dist[vecin] = dist[nodCurent] + costVecin;
        }
    }

    for (i=nodInit; i<=n; i++)
    {
        int nodCurent = i;
        int nrvecini = G[i].size();
        for (int j=0; j<nrvecini; j++)
        {
            int vecin = G[i][j].first;
            int costVecin = G[i][j].second;

            if (dist[nodCurent] + costVecin < dist[vecin])
            {
                ok=false;
                return;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> cost;
        G[x].push_back({y, cost});
    }

    memset(dist, oo, sizeof(dist));
    dist[1] = 0;
    belFrd(1);

    if (ok)
    {
        for (i=2; i<=n; i++)
            fout << dist[i] << " ";
    }

    else
        fout << "Ciclu negativ!";

    return 0;
}