#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;

const int Nmax = 50333;
const int Mmax = 250555;

vector<pii> G[Nmax];

char inQueue[Nmax];
int dist[Nmax];
int cnt[Nmax];


int main()
{
  ifstream f ("bellmanford.in");
  ofstream g ("bellmanford.out");
  
  int N, M, a, b, c;
  f >> N >> M;
  for (int i = 0; i < M; i++) {
    f >> a >> b >> c;
    a--, b--;
    G[a].push_back(make_pair(b, c));
  }
  memset(dist, 0x3f, sizeof(dist));
  queue<int> Q;
  dist[0] = 0;
  Q.push(0);
  inQueue[0]= 1;
  bool ciclu = 0;
  
  while(!Q.empty() && !ciclu) {
    int a = Q.front();
    Q.pop();
    inQueue[a] = 0;
    
    for (auto P: G[a]) {
      if (dist[P.first] > dist[a] + P.second) {
        cnt[P.first]++;
        if (cnt[P.first] > N-1) {
          ciclu = 1;
          break;
        }
        dist[P.first] = dist[a] + P.second;
        if (!inQueue[P.first]) {
          Q.push(P.first);
          inQueue[P.first] = 1;
        }
      }
    }
  }
  
  if (ciclu)
    g << "Ciclu negativ!\n";
  else
    for (int a = 1; a < N; a++) {
      g << dist[a] << (a < N-1 ? ' ' : '\n');
    }

  return 0;
}