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

using namespace std;

struct Muchie {
    int end;
    int cost;
};

const int INFTY = 1000000000;

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

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

    vector<vector<Muchie>> graf(n + 1);
    for (int i = 0; i < m; ++i) {
        int start, end, cost;
        in >> start >> end >> cost;

        graf[start].push_back({end, cost});
    }

    // vectorul cu rezultatul
    vector<int> distante(n + 1, INFTY);

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

    // retin nodurile care s-au relaxat,
    // pentru a le refolosi la pasul urmator
    set<int> relaxate;

    // initial doar sursa poate fi folosita
    relaxate.insert(1);

    for (int k = 1; k <= n - 1; ++k) {
        set<int> noi_relaxate;

        // iau doar nodurile care au fost actualizate
        for (int nod : relaxate) {

            for (auto muchie : graf[nod]) {
                // relaxare muchie

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

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

        relaxate = noi_relaxate;
    }

    ofstream out("bellmanford.out");

    for (int nod = 1; nod <= n; ++nod) {
        for (auto muchie : graf[nod]) {
            int cost_vechi = distante[muchie.end];
            int cost_nou = distante[nod] + muchie.cost;

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

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