#include <iostream>
#include <cstdio>

using namespace std;

//definesc o variabila constanta. 2e29 inseamna 2 la puterea 29 (fac asta pentru ca un int are pana la 2^31 biti, si daca adun INF CU INF sa nu am overflow)
const int INF = 2e28;

//In principiu nu e bine sa folosesti variabile globale, dar 
//acum imi e mai rapid sa scriu asa.
int n, m;
int cost[100][100];
int distanta[100];
int parinte[100];

void initializare(){
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            cost[i][j] = INF;
        }
    }
    for(int i = 0; i < 100; i++){
        distanta[i] = INF;
        parinte[i] = INF;
    }
    distanta[0] = 0;
    parinte[0] = 0;
}

void citire(){
    //n - nr noduri
    //m - nr muchii
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        //muchie de la nodul x la nodul y, avand costul cost
        int x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        cost[x][y] = z;
    }
}

void relax(int nod1, int nod2){
    if(distanta[nod2] > distanta[nod1] + cost[nod1][nod2]){
        distanta[nod2] = distanta[nod1] + cost[nod1][nod2];
        parinte[nod2] = nod1;
    }
}

bool bellman(){
    for(int k = 0; k < n - 1; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(cost[i][j] != INF){
                    //Muchie de la nodul i la nodul j
                    relax(i, j);
                }
            }
        }        
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(cost[i][j] != INF){
                if(distanta[j] > distanta[i] + cost[i][j]){
                    return false;
                }
            }
        }
    }
    return true;
}

void afisare(){
    for(int i = 1; i < n; i++){
        cout << distanta[i] << " ";
    }
}

int main(){
    freopen("date.in", "r", stdin);

    initializare();
    citire();
    if(bellman()){
        afisare();
    }
    else{
        cout << "Ciclu negativ!";
    }

    return 0;
}