#include <cstdio>
#include <cstring>
#define source 1
#define NMAX 50001
#define INF (1<<20)

using namespace std;

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

int N, M;
int D[NMAX], Prev[NMAX];

struct list {
    int cost, inf;
    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 i;
    Init();
    for(int k = 1; k <= N - 1; ++ k)
        for(i = 1; i <= N; ++ i)
            for(it = G[i]; it; it = it->next)
                Relax(i, it->inf, it->cost);

    for(i = 1; i <= N; ++ i)
        for(it = G[i]; it; it = it->next)
            if(Relax(i, it->inf, it->cost)) {
                fprintf(fout, "Ciclu negativ!\n");
                it = 0; i = N + 1;
                return ;
            }

    for(i = 2; i <= N; ++ i)
        fprintf(fout, "%d ", D[i]);
    fprintf(fout, "\n");
}

void showEdge() {
    list *it;
    for(int i = 1; i <= N; ++ i) {
        fprintf(fout, "%d - ", i);
        for(it = G[i]; it; it = it->next)
            fprintf(fout, "%d ", it->inf);
        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;
}