#include <bits/stdc++.h>

using namespace std;

vector <int> DISTANTA(50010);
vector <pair <int, int> > ADJACENT[10000];
queue <int> COADA;

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

    for(int i = 1; i <= muchii; i++){
        int x, y, cost;
        fin >> x >> y >> cost;

        ADJACENT[x].push_back(make_pair(y, cost));
    }

    for(int i = 1; i <= noduri; i++)
        DISTANTA[i] = 1e9;

    ofstream fout("bellmanford.out");
    vector <int> Numar(10000);
    COADA.push(1);
    DISTANTA[1] = 0;
    while(!COADA.empty()){
        int plec  = COADA.front();
        COADA.pop();
        Numar[plec] ++;
        if(Numar[plec] > noduri - 1){
            fout << "Ciclu negativ!";
            return 0;
        }

        for(auto it: ADJACENT[plec]){
            if(DISTANTA[plec] + it.second < DISTANTA[it.first]){
                DISTANTA[it.first] = DISTANTA[plec] + it.second;
                COADA.push(it.first);
            }
        }
    }

    for(int i = 2; i <= noduri; i++)
        fout << DISTANTA[i] << " ";

    return 0;
}