#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#define maxi 50001
#define infinite 99999999

using namespace std;

vector< tuple<int,int,int> > L;
int dist[maxi];
int n, m , x, y ,c;


int main()
{
    cin >> n >> m;
    for( int i = 1 ; i <= m ; i++ )
    {
        cin >> x >> y >> c;
        L.push_back( make_tuple(x, y , c) );
    }

    for( int i = 1 ; i <= n ; i++ )
            dist[i] = infinite;

    dist[1] = 0;

    for( int i = 1 ; i < n ; i++ )
    {
        for( auto it : L )
        {
            int src , dest, cost;
            tie(src, dest, cost) = it;
            dist[dest] = min( dist[dest] , dist[src] + cost );
        }
    }

    for( auto it : L )
    {
        int src , dest, cost;
        tie(src, dest, cost) = it;
        if( dist[dest] > dist[src] + cost )
        {
            cout << "Ciclu negativ!";
            return 0;
        }
    }

    for( int i = 2 ; i <= n ; i++ )
        cout << dist[i] << " ";
    return 0;
}