#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct edge{ int dr,c; }edg;
bool inserted[50003];
vector< struct edge > v[50003];
int used[500003],d[50003];
queue <int> q;
int n,m,i,j,x,nod,cost;
int main()
{
    in>>n>>m;
    for( i = 0 ; i < m ; i ++ )
    {
        in >> x >> edg.dr >> edg.c ;
        v[x].push_back( edg );
    }
    for( i = 1 ; i <= n ; i ++)
    {
        used[i] = 0;
        d[i] = 1<<30;
        inserted[ i ] = false;
    }
    inserted[ 1 ] = true;
    d[ 1 ] = 0;
    q.push( 1 );
    while( ! q.empty() )
    {
        nod = q.front();
        inserted[ nod ] = false;
        q.pop();
        for(auto it = v[nod].begin() ; it != v[nod].end(); it ++)
            if (  d[ nod ] + it->c <d[ it->dr ] )
            {
                d[ it->dr ] =  d[ nod ] + it->c ;
                if (!inserted[it->dr] )
                {
                    cost = it->c;
                    used[ it->dr ]++;
                    q.push(it->dr);
                    inserted[ it->dr ] = true ;
                   if (used[it->dr] >= n)
                   {
                       out << "Ciclu negativ!";
                       return 0;
                   }
                }
            }
    }
    for( i = 2 ; i <= n ; i ++)
        if (d[ i ] == 1<<30)
            out << 0 << " " ;
        else
            out << d[i ] << " ";
    return 0;
}