#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 ]) && (!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;
               }
               d[ it->dr ] =  d[ nod ] + it->c ;
            }
    }
    for( i = 2 ; i <= n ; i ++)
        if (d[ i ] == 1<<30)
            out << 0 << " " ;
        else
            out << d[i ] << " ";
    return 0;
}