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

using namespace std;

#define kNMAX 50001
#define kMAX 1005

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);
}

void BellmanFord(){

    if (ultim - prim == -1)    return;
    int 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]++;
            if (frecventa[x] > N ){
                cicluNegativ = true;
                return;
            }

        }

    }
    BellmanFord();
    return;


}


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();
    BellmanFord();
    outOfHere:
    for (int i = 2; i <= N && !cicluNegativ; i++){

        out << distanta[i] << " ";
    }
    if (cicluNegativ)   out << "Ciclu negativ!" << endl;


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