#include <bits/stdc++.h>

using namespace std;

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

vector <bell> ADJACENT;
vector <long long > DISTANTA(50010);

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] = 1e12;
    
    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");
    
    for(int i = 1; i <= noduri; i++){
        for(auto it: ADJACENT)
            if(DISTANTA[it.plec] + it.cost < DISTANTA[it.maDuc]){
                fout << "Ciclu negativ!";
                return 0;
            }
    }
    
    for(int i = 2; i <= noduri; i++)
        fout << DISTANTA[i] << " ";

    return 0;
}