#include<fstream>
#include<queue>
#include<vector>
using namespace std;

fstream in ( "bellmanford.in" , ios::in ),
        out( "bellmanford.out", ios::out);

struct muchie{
    int varf, cost;
};

bool incoada[50001], gasit;
int n, m, contqueue[50001], val[50001];
queue <int> coada;

vector <muchie> v[50001];


void bfs(int nod){

    size_t i;

    coada.push( nod );
    incoada[nod] = true;
    contqueue[nod]++;

    while( ! coada.empty() ){

        nod = coada.front();
        coada.pop();
        incoada[nod] = false;
        for( i=0; i<v[nod].size() ; i++ ){

            if( val[nod] + v[nod][i].cost < val[ v[nod][i].varf ] || contqueue[ v[nod][i].varf ] == 0 ){

                if( !incoada[ v[nod][i].varf] )
                {
                    coada.push( v[nod][i].varf );
                    incoada[ v[nod][i].varf ] = true;
                    contqueue[ v[nod][i].varf ]++;
                }

                val[ v[nod][i].varf ] = val[nod] + v[nod][i].cost;

                if( contqueue[ v[nod][i].varf ] == n ){

                        gasit = true;
                        return;
                }
            }
        }
    }
}


int main(){

    int x, y, c;
    muchie a;

    in >> n >> m;

    for(int i=1; i<=m; i++){

        in >> x >> y >> c;

        a.cost = c;
        a.varf = y;
        v[x].push_back( a );

    }

    bfs (1);

    if (gasit){

        out <<"Ciclu negativ!\n";
    }
    else {

        for(int i=2; i<=n; i++){

            out << val[i] <<' ';
        }
    }

    return 0;
}