#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define Nmax 50001
#define INF 1<<30
using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

int n, m, w[ Nmax ], d[ Nmax ];
queue < int > q;
vector < pair < int, int > > a[ Nmax ];
vector < pair < int, int > > :: iterator it;

int main()
{
    int x, y, k;

    f >> n >> m;

    for ( int i = 1; i <= m; ++ i )
    {
        f >> x >> y >> k;
        a[ x ].push_back( make_pair( y, k ) );
    }

    for (int i = 2; i <= n; ++ i )
        d[ i ] = INF;

    q.push( 1 );
    d[ 1 ] = 0;

    while ( !q.empty() )
    {
        x = q.front();
        q.pop();

        for ( it = a[ x ].begin(); it != a[ x ].end(); ++ it )
        {
            if ( d[ it -> first ] > d[ x ] + it -> second )
            {
                d[ it -> first ] = d[ x ] + it -> second;
                q.push( it -> first );

                w[ it -> first ] ++;
                if ( w[ it -> first ] >= n )
                {
                    g << "Ciclu negativ!\n";
                    return 0;
                }
            }
        }
    }
    for ( int i = 2; i <= n; ++ i )
        g << d[ i ] << " ";
    return 0;
}