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

using namespace std;

struct Muchie {
    int cost;
    int start, end;
};

const int INFTY = 1000000000;

int main() {
    ifstream in("bellmanford.in");

    int n, m;
    in >> n >> m;

    vector<int> distante(n + 1, INFTY);

    // 1 este sursa
    distante[1] = 0;

    vector<Muchie> muchii(m);
    for (int i = 0; i < m; ++i) {
        in >> muchii[i].start >> muchii[i].end >> muchii[i].cost;
    }

    for (int k = 1; k <= n - 1; ++k) {
        for (auto muchie : muchii) {
            // relaxare muchie

            int cost_vechi = distante[muchie.end];
            int cost_nou = distante[muchie.start] + muchie.cost;

            if (cost_nou < cost_vechi) {
                distante[muchie.end] = cost_nou;
            }
        }
    }

    ofstream out("bellmanford.out");

    for (auto muchie : muchii) {
        int cost_vechi = distante[muchie.end];
        int cost_nou = distante[muchie.start] + muchie.cost;

        if (cost_nou < cost_vechi) {
            out << "Ciclu negativ!\n";
            return 0;
        }
    }

    for (int i = 2; i <= n; ++i) {
        out << distante[i] << ' ';
    }
}