#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define LMAX 50010

struct Muchie {
    int n,c;
    Muchie() {n=c=0;};
    Muchie(int nod, int cost) {
        n = nod;
        c = cost;
    }
};

int N,M;
int C[LMAX], cnt[LMAX];
vector<Muchie> V[LMAX];
queue<int> Q;
bool viz[LMAX];

void citire() {
    scanf("%d %d", &N, &M);
    for (int x,y,c; M; --M) {
        scanf("%d %d %d", &x, &y, &c);
        V[x].push_back(Muchie(y,c));
    }
}

void bellman() {
    int n;
    Muchie k;
    Q.push(1);

    while (!Q.empty()) {
        n = Q.front();
        Q.pop();
        viz[n] = false;
        for (int i=0, e=V[n].size(); i<e; ++i) {
            k = V[n][i];

            if (C[k.n] > C[n] + k.c || !C[k.n]) {
                C[k.n] = C[n] + k.c;

                if (!viz[k.n]) {
                    if (cnt[k.n] > N) {
                        printf("Ciclu negativ!\n");
                        exit(0);
                    }
                    Q.push(k.n);
                    ++cnt[k.n];
                    viz[k.n] = true;
                }
            }
        }
    }
}

int main () {

    freopen("bellmanford.in","rt",stdin);
    freopen("bellmanford.out","wt",stdout);

    citire();
    bellman();

    for (int i=2; i<=N; ++i)
        printf("%d ", C[i]);

    return 0;
}