#include <bits/stdc++.h>

using namespace std;

struct bell{
    int plec;
    int maDuc;
    int cost;
};

vector <bell> ADJACENT;
vector <int> DISTANTA(50000);

int main()
{
    ifstream fin("bellmanford.in");
    int noduri, muchii;

    fin >> noduri >> muchii;

    for(int i = 1; i <= noduri; i++){
        int x, y, cost;
        fin >> x >> y >> cost;
        
        bell aux;
        aux.plec = x;
        aux.maDuc = y;
        aux.cost = cost;

        ADJACENT.push_back(aux);
    }    

    for(int i = 1; i <= noduri; i++)
        DISTANTA[i] = 1e9;
    
    DISTANTA[1] = 0;
    for(int i = 1; i <= noduri; i++){
        for(auto it: ADJACENT)
            if(DISTANTA[it.plec] + it.cost < DISTANTA[it.maDuc]){
                DISTANTA[it.maDuc] = DISTANTA[it.plec] + it.cost;
            }
    }

    ofstream fout("bellmanford.out");
    int sum = 0;
    for(int i = 2; i <= noduri; i++){
        //fout << DISTANTA[i] << " ";
        sum += DISTANTA[i];
    }

    //--------------------------------------

    for(int i = 1; i <= noduri; i++)
        DISTANTA[i] = 1e9;
    
    DISTANTA[1] = 0;
    for(int i = 1; i <= noduri; i++){
        for(auto it: ADJACENT)
            if(DISTANTA[it.plec] + it.cost < DISTANTA[it.maDuc]){
                DISTANTA[it.maDuc] = DISTANTA[it.plec] + it.cost;
            }
    }
    
    int sum2 = 0;
    for(int i = 2; i <= noduri; i++){
        //fout << DISTANTA[i] << " ";
        sum2 += DISTANTA[i];
    }

    if(sum != sum2)
        fout << "Ciclu negativ!";
    else{
        for(int i = 2; i <= noduri; i++)
            fout << DISTANTA[i] << " ";
    }


    return 0;
}