#include <cstdio>
#include <cstring>
#define source 1
#define NMAX 50005
#define MMAX 250005
#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];

struct list {
    int u, v, cost;
} E[MMAX];

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() {
    int i, j;
    Init();
    for(i = 1; i <= N - 1; ++ i)
        for(j = 1; j <= M; ++ j)
            Relax(E[j].u, E[j].v, E[j].cost);
    for(j = 1; j <= M; ++ j)
        if(Relax(E[j].u, E[j].v, E[j].cost)) {
            fprintf(fout, "Ciclu negativ!\n");
            j = K + 1;
            return ;
        }
    for(i = 2; i <= N; ++ i)
        fprintf(fout, "%d ", D[i]);
    fprintf(fout, "\n");
}

void showEdges() {
    for(int i = 1; i <= M; ++ i)
        fprintf(fout, "%d %d %d\n", E[i].u, E[i].v, E[i].cost);
}

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", &E[i].u, &E[i].v, &E[i].cost);
}

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