#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <stdlib.h>

using namespace std;

#define kNMAX 50011
#define kMAX 1<<30

struct muchie{

    int destinatie;
    int cost;
};
bool prezentCoada[kNMAX], cicluNegativ = false;
vector<muchie> vecini[kNMAX];
int distanta[kNMAX],coada[kNMAX], frecventa[kNMAX];
int N, M, prim, ultim, maxSteps, i;
fstream in, out;

void initializare(){

    distanta[1] = 0;
    for (int i = 2; i <= N; i++){
        distanta[i] = kMAX;
    }
    coada[1] = 1;
    prim = 0;
    ultim = 1;
    maxSteps = log2(N);
    //fill(frecventa, frecventa + N, 0);
}

bool BellmanFord(){

    int x = coada[prim];
    while (frecventa[x] > N){
        if (ultim - prim == -1)    return true;
        x = coada[++prim];
        prezentCoada[x] = 0;
        for (int i = 0; i < vecini[x].size(); i++){

            muchie tempMuchie = vecini[x][i];
            if (distanta[x] + tempMuchie.cost < distanta[tempMuchie.destinatie] ){

                if (!prezentCoada[tempMuchie.destinatie])
                    coada[++ultim] = tempMuchie.destinatie;
                distanta[tempMuchie.destinatie] = distanta[x] + tempMuchie.cost;
                frecventa[x]++;

            }

        }
    }
    return false;


}


int main(){


    in.open("bellmanford.in", ios::in);
    out.open("bellmanford.out", ios::out);

    in >> N >> M;
    for (int i = 1; i <= M; i++){

        int tempAux;
        muchie tempMuchie;
        in >> tempAux >> tempMuchie.destinatie >> tempMuchie.cost;
        vecini[tempAux].push_back(tempMuchie);
    }

    initializare();
    bool ok = BellmanFord();
    if (!ok)   out << "Ciclu negativ!" << endl;
        else
            for (int i = 2; i <= N && !cicluNegativ; i++)
                out << distanta[i] << " ";



    in.close();
    out.close();
    return 0;
}