#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

struct muchie{
    int nod, cost;
};

struct muchieComp{
    int nod1, nod2, cost;
};

bool operator<(muchie a, muchie b){
    return a.cost < b.cost;
}

const int mxN = 101, oo = 0x3F3F3F3F;

vector<muchie> G[mxN];
vector<muchieComp> G2;

int n, m, p;
bool viz[mxN];
int drum[mxN];
bool cicluNeg = false;

void citire(){
    int a, b, c;
    fin >> n >> m;

    while(fin >> a){
        fin >> b >> c;
        G2.push_back({a, b, c});
    }
}
struct comp{
    bool operator()(int a, int b){
        return drum[a] < drum[b];
    }
};

void Belman(){
    drum[1] = 0;

    for(int i = 1; i < n; i++){
        for(auto m : G2){
            if(drum[m.nod2] > drum[m.nod1] + m.cost)
                drum[m.nod2] = drum[m.nod1] + m.cost;
        }
    }

    for(auto m : G2){
        if(drum[m.nod2] > drum[m.nod1] + m.cost){
            drum[m.nod2] = drum[m.nod1] + m.cost;
            cicluNeg = true;
        }
    }
}

void afisare(){
    if(cicluNeg){
        fout << "Ciclu negativ!";
        return;
    }
    for(int i = 2; i <= n; i++){
        fout << drum[i] << " ";
    }
}

int main()
{
    citire();

    for(int i = 1; i <= n; i++)
        drum[i] = oo;

    Belman();

    afisare();
    return 0;
}