#include <iostream>
#include <fstream>
#define  NMAX 50002
#define INFIN 1<<30

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct elem{
    int val, cos;
    elem *urm;
}*v[NMAX];

int n, m;
int costDrum[NMAX];
bool validare;
int pus[NMAX];

void citire(){
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        in >> x >> y >> c;
        elem *deAdaugat = new elem;
        deAdaugat -> val = y;
        deAdaugat -> cos = c;
        deAdaugat -> urm = v[x];
        v[x] = deAdaugat;
    }
}

void bellmanford(){
    int coada[NMAX], primul, ultimul;
    bool pusInCoada[NMAX];
    for(int i = 1; i <= n; i++){
        costDrum[i] = INFIN;
        pusInCoada[i] = false;
    }
    primul = ultimul = 1;
    coada[primul] = 1;
    pusInCoada[1] = true;
    costDrum[1] = 0;
    while (primul <= ultimul){
        int nodActual = coada[primul];
        pus[nodActual]++;
        if(pus[nodActual] == n){
            validare = true;
            break;
        }
        primul++;
        elem* parcurg = v[nodActual];
        while(parcurg != NULL){
            if(costDrum[parcurg -> val] > costDrum[nodActual] + parcurg -> cos){
                    costDrum[parcurg -> val] = costDrum[nodActual] + parcurg -> cos;
                    if(pusInCoada[parcurg -> val] == false){
                        coada[++ultimul] = parcurg -> val;
                        pusInCoada[parcurg ->val] = true;
                    }
            }
            parcurg = parcurg -> urm;
        }
    }
}

void afisare(){
    for(int i = 2; i <= n; i++){
        out << costDrum[i]<<' ';
    }
}

int main() {
    citire();
    bellmanford();
    if(validare == true){
        out<<"Ciclu negativ!";
    }else{
        afisare();
    };
    return 0;
}