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

/*
 *
 */
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< int > > v;
vector< int >::const_iterator it, iend;
inline void swap( int& x, int& y )
{
    int aux=x;
    x=y;
    y=aux;
}
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]]=0;
    --N;
    DownHeap(1);
}
inline void insert( int vertex )
{
    Heap[++N]=vertex;
    Position[vertex]=N;
    UpHeap( N );
}
int main( void )
{
    long long int p;
    int n, m, x, y, c, i;
    ifstream in( "bellmanford.in" );
    in>>n>>m;
    v.resize(n);
    for(  i=0;  i < m; ++i )
    {
        in>>x>>y>>c;
        Edge.push_back( vertex( x-1, y-1, c ) );
        v[x-1].push_back( i );
    }
    for( i=1; i < n; ++i )
        d[i]=inf;
    p=1LL*n*m;
    while( N && p )
    {
        --p;
        x=Heap[1];
        cut_root();
        for( it=v[x].begin(), iend=v[x].end(); it < iend; ++it )
            if( d[Edge[*it].x]+Edge[*it].c < d[Edge[*it].y] )
            {
                d[Edge[*it].y]=d[Edge[*it].x]+Edge[*it].c;
                if( !Position[Edge[*it].y] )
                    insert( Edge[*it].y );
            }
    }
    for( i=0; i < m; ++i )
        if( d[Edge[i].x] + Edge[i].c < d[Edge[i].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;
}