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

using namespace std;

#define NMAX 50001
#define INFINIT 0x3F3F3F3F

struct Nod
{
    int distanta;
    vector< pair<int, short> > muchii;
};

Nod noduri[NMAX];
bitset<NMAX> inCoada;

bool cicluNegativ(int n);

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

    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        noduri[x].muchii.push_back(make_pair(y, (short)c));
    }

    for (int i = 1; i <= n; ++i) {
        noduri[i].distanta = INFINIT;
    }

    if (cicluNegativ(n)) {
        fout << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= n; ++i) {
            fout << noduri[i].distanta << " ";
        }
    }


    return 0;
}

bool cicluNegativ(int n)
{
    long long ramas = 1LL * n * (n - 1);
    queue<int> q;

    q.push(1);
    noduri[1].distanta = 0;

    while (!q.empty() && ramas > 0) {
        int curent = q.front();
        q.pop();

        inCoada[curent] = false;

        for (auto muchie : noduri[curent].muchii) {
            int vecin = muchie.first;
            int costNou = noduri[curent].distanta + (int)muchie.second;

            if (costNou < noduri[vecin].distanta) {
                noduri[vecin].distanta = costNou;
                if (!inCoada[vecin]) {
                    q.push(vecin);
                    inCoada[vecin] = true;
                }
            }

            --ramas;
        }
    }

    return !q.empty();
}