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

const int max = 1 << 30;

struct muchie {
    int destinatie;
    int valoare;
};
std::vector<muchie> noduri[50001];
int distanta[50001];
bool iiGata[50001];
int ciclu[50001];

int main() {
    std::ifstream f("bellmanford.in");
    int n, m;
    f >> n >> m;

    int x, y, c;
    for (int i=0; i<m; ++i) {
        f >> x >> y >> c;
        muchie m; m.destinatie=y; m.valoare=c;
        noduri[x].push_back(m);
    }

    // for (int i=1; i<=n; ++i) {
    //     std::cout << i << "\n\t";
    //     for (int j=0; j<noduri[i].size(); ++j) {
    //         std::cout << noduri[i][j].destinatie << " ";
    //     }
    //     std::cout << "\n";
    // }

    for (int i=2; i<=n; ++i) {
        distanta[i] = max;
    }

    std::ofstream g("bellmanford.out");

    std::queue<int> lista;
    lista.push(1);
    distanta[1] = 0;
    while (!lista.empty()) {
        int x = lista.front();
        lista.pop();

        iiGata[x] = 0;
        for (int i=0; i<noduri[x].size(); ++i) {
            int drum = distanta[x] + noduri[x][i].valoare;
            if (drum < distanta[noduri[x][i].destinatie]) {
                distanta[noduri[x][i].destinatie] = drum;

                if (!iiGata[noduri[x][i].destinatie]) {
                    iiGata[noduri[x][i].destinatie] = 1;
                    lista.push(noduri[x][i].destinatie);

                    ++ciclu[noduri[x][i].destinatie];
                    if (ciclu[noduri[x][i].destinatie] > n) {
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for (int i=2; i<=n; ++i) {
        if (distanta[i] != max) g << distanta[i] << " ";
        else g << "0 ";
    }
    return 0;
}