// Mihai Priboi

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define MAXN 50000
#define MAXM 250000
#define INF (int)1e9

struct Edge {
  int node, cost;
};

struct Node {
  vector<Edge> child;
  int val, counter;
  bool inQueue;
};

Node v[MAXN + 1];

int main() {
  FILE *fin, *fout;
  int n, m, i, x, y, c, node;
  bool cicle;
  fin = fopen( "bellmanford.in", "r" );

  fscanf( fin, "%d%d", &n, &m );
  for( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d%d", &x, &y, &c );
    v[x].child.push_back({y, c});
  }

  fclose( fin );

  for( i = 2; i <= n; i++ )
    v[i].val = INF;

  queue<int> myQueue;
  myQueue.push(1);
  v[1].inQueue = true;
  v[1].counter++;
  cicle = false;

  while( !myQueue.empty() && !cicle ) {
    node = myQueue.front();
    myQueue.pop();
    v[node].inQueue = false;

    for( auto x : v[node].child ) {
      if( v[node].val + x.cost < v[x.node].val ) {
        v[x.node].val = v[node].val + x.cost;
        if( ++v[x.node].counter >= n )
          cicle = true;
        
        if( !v[x.node].inQueue ) {
          myQueue.push(x.node);
          v[x.node].inQueue = true;
        }
      }
    }
  }

  fout = fopen( "bellmanford.out", "w" );

  if( cicle )
    fprintf( fout, "Ciclu negativ!" );
  else
    for( i = 2; i <= n; i++ )
      fprintf( fout, "%d ", v[i].val );

  fclose( fout );
  return 0;
}