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

void citire(std::vector<std::vector<std::pair<int, int> > > &graf, int &n) {
    int m;
    int i, j, w;
    std::ifstream f("bellmanford.in");
    f >> n >> m;
    graf.resize(n);
    while (m--) {
        f >> i >> j >> w;
        graf[i - 1].emplace_back(j - 1, w);
    }
    f.close();
}

void bellmanFord() {
    std::vector<std::vector<std::pair<int, int> > > graf;
    int n;
    citire(graf, n);

    std::vector d(n, INT_MAX);
    std::vector tata(n, -1);
    std::queue<int> q;
    std::vector inCoada(n, false);
    std::vector lungime(n, 0);
    d[0] = 0;
    q.push(0);
    inCoada[0] = true;

    while (!q.empty()) {
        const int u = q.front();
        q.pop();
        inCoada[u] = false;
        for (const auto &[v, w]: graf[u])
            if (d[u] + w < d[v]) {
                lungime[v] = lungime[u] + 1;
                if (lungime[v] > n - 1) {
                    std::ofstream g("bellmanford.out");
                    g << "Ciclu negativ!";
                    g.close();
                    return;
                }
                d[v] = d[u] + w;
                tata[v] = u;
                if (!inCoada[v]) {
                    q.push(v);
                    inCoada[v] = true;
                }
            }
    }

    std::ofstream g("bellmanford.out");
    for (int i = 1; i < n; ++i)
        g << d[i] << " ";
    g.close();
}

int main() {
    bellmanFord();
    return 0;
}