#include <vector>
#include <tuple>
#include <iostream>
#include <fstream>

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

static const int mxn = 50e3, INF = 0x3f3f3f3f;
std::vector< std::tuple<int, int, int> > edges;
int n, m;
int distance[mxn + 5];

int main(){
  fin >> n >> m;
  for (int t = 1; t <= m; ++t){
    int a, b, d;
    fin >> a >> b >> d;
    edges.push_back({a, b, d});
  }

  for (int i = 1; i <= n; ++i){
    distance[i] = INF;
  }
  distance[1] = 0;
  for (int i = 1; i < n; ++i){
    for (auto e : edges){
      int a, b, w;
      std::tie(a, b, w) = e;
      distance[b] = std::min(distance[b], distance[a] + w);
    }
  }

  for (auto e : edges){
    int a, b, w;
    std::tie(a, b, w) = e;
    if (distance[a] != INF && (distance[a] + w < distance[b])){
      fout << "Ciclu negativ!\n";
      return 0;
    }
  }

  for (int i = 2; i <= n; ++i){
    fout << distance[i] << ' ';
  }
  fout << '\n';
  return 0;
}