#include <bits/stdc++.h>

using namespace std;

const int Nmax = 250001;
const int INF = 1e9;
int dist[Nmax];
queue< int > q;

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

int main()
{
    int m, i, u, v, cost, j, cnt;
    long long n;
    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;

    q.push( 1 );
    cnt = 0;
    while ( !q.empty() && cnt < n * n ) {
      j = q.front();
      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;
            q.push( adj[j][i].first );
          }
      q.pop();
      cnt++;
    }

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

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

    return 0;
}