#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF (1<<31) - 1
using namespace std;

int N, M;

struct muchie{
    int y, c;
};
vector<muchie> vf[NMAX];
queue<int> coada;
int contor[NMAX], distanta[NMAX];

muchie y;

int minim(int a, int b){
    if(a > b){
        return b;
    }
    return a;
}

bool bfs(){
    int x, i;
    coada.push(1); contor[1] = 1;
    while(!coada.empty()){
        x = coada.front();
        coada.pop();
        for(i = 0; i < vf[x].size(); i++){
            y = vf[x][i];
            if(distanta[y.y] > distanta[x] + y.c){
                coada.push(y.y);
                contor[y.y]++;
                if(contor[y.y] == N){
                    return 0;
                }
                distanta[y.y] = distanta[x] + y.c;
            }
        }
    }
    return 1;
}

int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &N, &M);
    int x, y, c, i;
    for(i = 1; i <= M; i++){
        scanf("%d%d%d", &x, &y, &c);
        vf[x].push_back((muchie){y, c});
    }
    for(i = 2; i <= N; i++){
        distanta[i] = INF;
    }
    if(bfs() == 0){
        printf("Ciclu negativ!");
    }else{
        for(i = 2 ; i <= N; i++){
            printf("%d ", distanta[i]);
        }
    }
    return 0;

}