#include <bits/stdc++.h>

using namespace std;

const int Nmax = 250001;
const int INF = 1e9;
int dist[Nmax];

vector< pair<int, int> > adj[Nmax];

int main()
{
    int n, m, i, u, v, cost, j, l;
    ifstream fin ( "bellmanford.in");
    ofstream fout ( "bellmanford.out" );

    fin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
      fin >> u >> v >> cost;
      adj[u].push_back( {v, cost} );
    }

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

    for ( l = 0; l < n - 1; l ++ ) {
      for ( j = 1; j <= n; j ++ )
        for ( i = 0; i < adj[j].size(); i ++  )
          if ( dist[j] != INF && dist[j] + adj[j][i].second < dist[ adj[j][i].first ] )
            dist[ adj[j][i].first ] = dist[j] + adj[j][i].second;
    }

    bool ok = true;
    for ( j = 1; j <= n; j ++ )
        for ( i = 0; i < adj[j].size(); i ++  )
          if ( dist[j] + adj[j][i].second < dist[ adj[j][i].first ] )
            ok = false;

    if ( !ok )
      fout << "Ciclu negativ!\n";
    else
      for ( i = 2; i <= n; i ++ )
        fout << dist[i] << " ";

    fin.close();
    fout.close();

    return 0;
}