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

/*
 *
 */
using namespace std;
struct vertex
{
    int x, y, c;
};
vector< int > d;
vector< vertex > v;
inline void operator>>( istream& in, vertex& A )
{
    in>>A.x>>A.y>>A.c;
    A.x-=1;
    A.y-=1;
}
int main()
{
    int n, m, i, j;
    ifstream in("bellmanford.in");
    in>>n>>m;
    copy( istream_iterator<vertex>(in), istream_iterator<vertex>(), back_inserter(v) );
    d.resize(n);
    d.assign( n, inf );
    d[0]=0;
    for( i=0; i < n; ++i )
    {
        for( j=0; j < m; ++j )
        {
            if( d[v[j].x]+v[j].c < d[v[j].y] )
                d[v[j].y]=d[v[j].x]+v[j].c;
        }
    }
    for( i=0; i < m; ++i )
        if( d[v[i].x]+v[i].c < d[v[i].y] )
        {
            ofstream out("bellmanford.out");
            out<<"Ciclu negativ!";
        }
    ofstream out("bellmanford.out");
    copy( d.begin()+1, d.end(), ostream_iterator<int>(out, " ")   );
    return 0;
}