/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 8, 2010, 6:14 PM
 */
#include <vector>
#include <fstream>
#include <iterator>
#define Nmax 50001

/*
 *
 */
using namespace std;
struct vertex
{
    int x, y, c;
    vertex( int a, int b, int d )
    {
        x=a;
        y=b;
        c=d;
    }
};
int N=1;
int Heap[Nmax], Position[Nmax], d[Nmax];
vector< vertex > Edge;
vector< vector< pair< int, int > > > v;
vector< pair< int , int > >::const_iterator it, iend;
inline void swap( int& x, int& y )
{
    x+=y;
    y=x-y;
    x-=y;
}
void DownHeap( int x )
{
    int son;
    for( ;; )
    {
        son=2*x;
        if( son > N )
            return;
        if( son < N && d[Heap[son]] >= d[Heap[son+1]] )
            ++son;
        if( d[Heap[son]] >= d[Heap[x]] )
            return;
        swap( Heap[son], Heap[x] );
        swap( Position[Heap[son]], Position[Heap[x]] );
        x=son;
    }
}
void UpHeap( int x )
{
    int key=d[Heap[x]], f=x/2;
    while( x > 1 && key < d[Heap[f]] )
    {
        swap( Heap[x], Heap[f] );
        swap( Position[Heap[x]], Position[Heap[f]] );
        x=f;
        f/=2;
    }
}
inline void cut_root()
{
    swap( Heap[1], Heap[N] );
    swap( Position[Heap[1]], Position[Heap[N]] );
    Position[Heap[N]]=-1;
    --N;
    DownHeap(1);
}
inline void insert( int vertex, int value )
{
    Heap[++N]=vertex;
    Position[vertex]=N;
    d[vertex]=value;
    UpHeap( N );
}
int main( void )
{
    int n, m, x, y, c;
    ifstream in( "bellmanford.in" );
    in>>n>>m;
    v.resize(n);
    for( ; m; --m )
    {
        in>>x>>y>>c;
        Edge.push_back( vertex( x-1, y-1, c ) );
        v[x-1].push_back( pair< int, int >( y-1, c ) );
    }
    while( N )
    {
        x=Heap[1];
        cut_root();
        for( it=v[x].begin(), iend=v[x].end(); it < iend; ++it )
        {
            if( !Position[it->first] )
            {
                insert( it->first, d[x]+it->second );
                continue;
            }
            if( -1 == Position[it->first] && d[it->first] > d[x]+it->second  )
               insert( it->first, d[x]+it->second );
        }
    }
    for( x=0; x < m; ++x )
        if( d[Edge[x].x] + Edge[x].c < d[Edge[x].y] )
        {
            ofstream out("bellmanford.out");
            out<<"Ciclu negativ!";
            return 0;
        }
    ofstream out("bellmanford.out");
    copy( d+1, d+n, ostream_iterator<int>(out, " ") );
    return 0;
}