#include <iostream>
#include <vector>
#include <fstream>
#include <deque>
#include <utility>
#include <queue>
using namespace std;

int n,m;

vector < vector < pair < int, int > > > lista_vecini;

vector < int > BellmanFord( int nod_pornire ){
    vector < int > distante(n+1, 9999999);
    vector < int > vizitat(n+1, 0);
    vector < int > apartineCoada(n+1, 0);
    queue < int > coada;
    int faraNeg = 1;

    coada.push(nod_pornire);
    apartineCoada[nod_pornire] = 1;
    distante[nod_pornire] = 0;
    while( !coada.empty() && faraNeg ){
        int x = coada.front();
        coada.pop();
        apartineCoada[x] = 0;

        for( int i = 1; i < lista_vecini[x].size(); i++ ){
            if( distante[x] + lista_vecini[x][i].second < distante[ lista_vecini[x][i].first ] ){
                distante[ lista_vecini[x][i].first ] = distante[x] + lista_vecini[x][i].second; //relaxam
                vizitat[ lista_vecini[x][i].first ]++;

                if( !apartineCoada[ lista_vecini[x][i].first ] ){
                    coada.push(lista_vecini[x][i].first);
                    apartineCoada[lista_vecini[x][i].first] = 1;
                }

                if( vizitat[ lista_vecini[x][i].first ] >= n ){
                    faraNeg = 0;
                }
            }
        }
    }
    if( faraNeg == 0 ){
        vector < int > lista_goala;
        return lista_goala;
    }
    return distante;
}


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

    fin >> n >> m;
    int intrare, iesire, cost;
    vector < pair < int,int > > x(1,make_pair(-1,-1));
    for( int i = 0; i <= n+1; i++ ){
        lista_vecini.push_back(x);
    }
    for( int i = 0; i <  m; i++ ){
        fin >> intrare >> iesire >> cost;
        lista_vecini[intrare].push_back(make_pair(iesire,cost));
    }
    vector < int > distante = BellmanFord(1);
    if( distante.size() != 0 ){
        for( int i = 2; i <= n; i++ ){
            fout << distante[i] << " ";
        }
    }
    else{
        fout << "Ciclu negativ!";
    }
    return 0;
}