#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>

using namespace std;

struct ncpair {
    int node;
    int cost;
    ncpair(int node_, int cost_): node(node_), cost(cost_) {}
};

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    int N, M;
    f >> N >> M;

    vector<ncpair> G[N];

    for (int i = 0; i < M; i++) {
        int a, b, c;
        f >> a >> b >> c;
        --a; --b;
        G[a].push_back(ncpair(b, c));
    }

    const int INF = 1e9 + 100;
    vector<int> cost(N, INF);
    vector<bool> inQ(N, false);
    vector<int> relaxed(N, 0);
    cost[0] = 0;
    inQ[0] = true;
    deque<int> Q;
    Q.push_back(0);

    while (!Q.empty()) {
        int node = Q.front();
        if (cost[Q.back()] < cost[node]) {
            node = Q.back();
            Q.pop_back();
        } else {
            Q.pop_front();
        }
        inQ[node] = false;
        relaxed[node]++;
        if (relaxed[node] >= N) {
            g << "Ciclu negativ!\n";
            f.close();
            g.close();
            return 0;
        }

        for (const ncpair& edge : G[node])
            if (cost[edge.node] > cost[node] + edge.cost) {
                cost[edge.node] = cost[node] + edge.cost;
                if (!inQ[edge.node]) {
                    Q.push_back(edge.node);
                    inQ[edge.node] = true;
                }
            }
    }

    for (int i = 1; i < N; i++)
        g << (cost[i] < INF ? cost[i] : 0) << ' ';
    g << '\n';

    f.close();
    g.close();
    return 0;
}