#include <cstdio>
#include <cstring>
#define source 1
#define NMAX 50005
#define MMAX 250005
#define XMAX 500005
#define INF (1<<20)

using namespace std;

FILE *fin = fopen("bellmanford.in", "r");
FILE *fout = fopen("bellmanford.out", "w");

int N, M, K;
int D[NMAX], U[NMAX], C[XMAX];

struct list {
    int inf, cost;
    list *next;
} *G[NMAX];

void addEdge(int u, int v, int cost) {
    list *Q = new list;
    Q->inf = v;
    Q->cost = cost;
    Q->next = G[u];
    G[u] = Q;
}

void Init() {
    for(int i = 2; i <= N; ++ i) D[i] = INF;
    D[source] = 0;
}

int Relax(int u, int v, int cost) {
    if(D[v] > D[u] + cost) {
        D[v] = D[u] + cost;
        return 1;
    }
    return 0;
}

void BellmanFord() {
    list *it;
    int l, r, nod;
    Init();
    C[l = r = 1] = 1;
    for(; l <= r; ++ l) {
        nod = C[l];
        for(it = G[nod]; it; it = it->next)
            if(Relax(nod, it->inf, it->cost)) {
                ++ U[nod];
                C[++ r] = it->inf;
                if(U[nod] > N) {
                    fprintf(fout, "Ciclu negativ!\n");
                    return ;
                }
            }
    }
    for(int i = 2; i <= N; ++ i)
        fprintf(fout, "%d ", D[i]);
    fprintf(fout, "\n");
}

void readData() {
    int i, j, u, v, cost;
    fscanf(fin, "%d %d", &N, &M);
    for(i = 1; i <= M; ++ i) {
        fscanf(fin, "%d %d %d", &u, &v, &cost);
        addEdge(u, v, cost);
    }
}

int main() {
    readData();
    BellmanFord();
    return 0;
}