#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct Vecin
{
    int y, c;

    Vecin(int _y, int _c)
    {
        y = _y, c = _c;
    }
};

int n, m, D[50001], C[50001];
vector<Vecin> G[50001];
bool gasit;

void Bellman()
{
    for (int i = 2; i <= n; ++i)
        D[i] = 0x3f3f3f3f;
    queue<int> Q;
    Q.push(1);
    while (!Q.empty())
    {
        int x = Q.front();
        ++C[x];
        if (C[x] == n)
        {
            gasit = true;
            return;
        }
        Q.pop();
        for (Vecin v : G[x])
        {
            if (D[x] + v.c < D[v.y])
            {
                D[v.y] = D[x] + v.c;
                Q.push(v.y);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].emplace_back(y, c);
    }
    Bellman();
    if (gasit)
        fout << "Ciclu negativ!";
    else
    {
        for (int i = 2; i <= n; ++i)
            fout << D[i] << " ";
    }

    return 0;
}