/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 9, 2010, 8:20 AM
 */
#include <queue>
#include <vector>
#include <fstream>
#include <iterator>
#define inf 0x3f3f3f3f

/*
 *
 */
using namespace std;
queue< int > Q;
vector< bool > inQ;
vector< int > d, nrinQ;
vector< vector< pair< int, int > > > v;
vector< pair< int, int > >::const_iterator it, iend;
int main( void )
{
    int n, m, x, y, c;
    ifstream in( "bellmanford.in" );
    in>>n>>m;
    v.resize(n);
    d.resize(n);
    d.assign( n, inf );
    for( ; m; --m )
    {
        in>>x>>y>>c;
        v[x-1].push_back( pair< int, int >( y-1, c ) );
    }
    d[0]=0;
    Q.push(0);
    inQ.resize(n);
    nrinQ.resize(n);
    inQ[0]=true;
    while( !Q.empty() )
    {
        x=Q.front(); Q.pop();
        inQ[x]=false;
        for( it=v[x].begin(), iend=v[x].end(); it < iend; ++it )
            if( d[x] + it->second < d[it->first]  )
            {
                d[it->first]=d[x]+it->second;
                if( !inQ[it->first] )
                {
                    if( nrinQ[it->first] > n )
                    {
                        ofstream out("bellmanford.out");
                        out<<"Ciclu negativ!";
                        return 0;
                    }
                    inQ[it->first]=true;
                    Q.push(it->first);
                    ++nrinQ[it->first];
                }
            }
    }
    ofstream out("bellmanford.out");
    copy( d.begin()+1, d.end(), ostream_iterator<int>(out, " ") );
    return 0;
}