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

#define LMAX 50010

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

int N, M;
vector<muchie> V[LMAX];
int C[LMAX];
queue<int> Q;
int in[LMAX], cnt_Q[LMAX];
bool viz[LMAX];

void bellman() {
    int n, L=1;
    Q.push(1);

    for (int i=0; i<L; ++i) {
        n = Q.front();
        Q.pop();
        for (int j=0, e=V[n].size(); j<e; ++j) {
            muchie k = V[n][j];
            viz[k.nod]=false;
            if (C[n] + k.cost < C[k.nod] || !C[k.nod]) {
                C[k.nod] = C[n] + k.cost;
                if (!viz[k.nod]) {
                    if (cnt_Q[k.nod]>in[k.nod]) {
                        printf("Ciclu negativ!");
                        exit(0);
                    }
                    Q.push(k.nod);
                    ++L;
                    ++cnt_Q[k.nod];
                    viz[k.nod]=true;
                }
            }

        }
    }
}

int main () {

    int x,y,c;

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

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        V[x].push_back(muchie(y,c));
        ++in[y];
    }

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