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

void BellmanFord( int nod_pornire, int n, vector < vector < pair < int, int > > > lista_vecini, vector < int > &distante ){
    vector < int > vizitat(n+1, 0);
    vector < int > apartineCoada(n+1, 0);
    deque < int > coada;
    int faraNeg = 1;

    coada.push_back(nod_pornire);
    apartineCoada[nod_pornire] = 1;
    distante[nod_pornire] = 0;
    while( coada.size() != 0 && faraNeg != 0 ){
        int x = coada[0];
        coada.pop_front();
        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 ] = 1;

                if( apartineCoada[ lista_vecini[x][i].first ] == 0 ){
                    coada.push_back(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 ){
        distante.clear();
    }
}


int main(){

    int n,m;
    vector < vector < pair < int, int > > > lista_vecini;
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin >> n >> m;
    vector < int > distante(n+1, 9999999);
    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));
    }
    BellmanFord( 1, n, lista_vecini, distante );
    if( distante.size() != 0 ){
        for( int i = 2; i <= n; i++ ){
            fout << distante[i] << " ";
        }
    }
    else{
        fout << "Ciclu negativ!";
    }
    return 0;
}