/*
    x0 - un varf de start

    cate un drum de cost minim de la x0 la fiecare celalalt varf al grafului.

    coada <- x

    cat timp (coada nu e vida) {
        - scot un varf x din coada
        - parcurg toti vecinii y ai lui x
        -   daca dmin[y] > dmin[x] + cost(x, y)
            dmin[y] = dmin[x] + cost(x, y);
            pred[y] = x
    }
*/

#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>

int bellmanford();
void citire();
void rezolvare();
void afisare();

FILE * fout;
std::vector< std::pair<int, int> > graf[50005];
std::queue < int > coada;
int dmin[50005], nr[50005], pred[50005];

int n, m;

int main() {
    fout = fopen("bellmanford.out", "w");

    citire();
    rezolvare();

    return 0;
}

void citire() {
    FILE * fin;
    int x, y, cost, i;

    fin = fopen("bellmanford.in", "r");

    fscanf(fin, "%d %d", &n, &m);

    for (i = 1; i <= m; i++) {
        fscanf(fin, "%d %d %d", &x, &y, &cost);

        graf[x].push_back(std::make_pair(y, cost));
    }

    fclose(fin);
}

void rezolvare() {
    if (!bellmanford()) {
        fprintf(fout, "Ciclu negativ!\n");
    } else {
        afisare();
    }
}

void afisare() {
    int i;

    fprintf(fout, "%d", dmin[2]);

    for (i = 3; i <= n; i++) {
        fprintf(fout, " %d", dmin[i]);
    }

    fprintf(fout, "\n");

    fclose(fout);
}

int bellmanford() {
    int i, x, y, c;

    for (i = 2; i <= n; i++) {
        dmin[i] = 10000000;
        pred[i] = 1;
    }

    coada.push(1);
    nr[1]++;

    while (!coada.empty()) {
        x = coada.front();
        coada.pop();

        for (i = 0; i < graf[x].size(); i++) {
            y = graf[x][i].first;
            c = graf[x][i].second;

            if (dmin[y] > dmin[x] + c) {
                dmin[y] = dmin[x] + c;
                pred[y] = x;

                coada.push(y);

                nr[y]++;

                if (nr[y] == n) {
                    return 0;
                }
            }
        }
    }

    return 1;
}