#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin( "bellmanford.in" );
ofstream fout( "bellmanford.out" );

const int MAXN = 50005;
const int INF = 1e9;

vector<pair<int, int>> G[MAXN];
queue<int> q;
int dist[MAXN], cnt[MAXN], n;
bool in_q[MAXN];

bool bellmanford( int src ) {
  q.push(src);
  in_q[src] = true;
  cnt[src] = 1;
  dist[src] = 0;

  while ( !q.empty() ) {
    int node = q.front();
    q.pop();
    in_q[node] = false;
    for ( auto ngh : G[node] ) {
      if ( dist[ngh.first] > dist[node] + ngh.second ) {
        dist[ngh.first] = dist[node] + ngh.second;
        if ( !in_q[ngh.first] ) {
          in_q[ngh.first] = true;
          q.push( ngh.first );
          ++cnt[ngh.first];
          if ( cnt[ngh.first] >= n ) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

int main() {
  int m, u, v, cst;

  fin >> n >> m;
  while ( m-- ) {
    fin >> u >> v >> cst;
    G[u].push_back({v, cst});
  }
  for ( int i = 1; i <= n; ++i ) {
    dist[i] = INF;
  }
  if ( bellmanford(1) ) {
    for ( int i = 2; i <= n; ++i ) {
      fout << dist[i] << " ";
    }
  } else {
    fout << "Ciclu negativ!";
  }
  fin.close();
  fout.close();
  return 0;
}