#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 500001, INF = 1 << 31 - 1;
int d[NMAX];

template <typename T>
struct triplet
{
  T from, to, cost;
};

template <typename T>
triplet<T> make_triplet(const T &m1, const T &m2, const T &m3)
{
  triplet<T> ans;
  ans.from = m1;
  ans.to = m2;
  ans.cost = m3;
  return ans;
}

vector<triplet<int>> edges;

int main()
{
  int n, m;
  in >> n >> m;
  // vrem sa pastram d[1] = 0;
  for (int i = 2; i <= n; i++)
  {
    d[i] = INF;
  }
  for (int i = 0; i < m; i++)
  {
    int from, to, cost;
    in >> from >> to >> cost;
    edges.push_back(make_triplet(from, to, cost));
  }

  for (int i = 1; i <= n - 1; i++)
  {
    for (auto edge : edges)
    {
      if (d[edge.from] + edge.cost < d[edge.to])
      {
        d[edge.to] = d[edge.from] + edge.cost;
      }
    }
  }

  bool has_neg_cycle = false;

  for (int i = 1; i <= n - 1 && !has_neg_cycle; i++)
  {
    for (auto edge : edges)
    {
      if (d[edge.from] + edge.cost < d[edge.to])
      {
        has_neg_cycle = true;
      }
    }
  }

  if (!has_neg_cycle)
  {
    for (int i = 2; i <= n; i++)
    {
      out << d[i] << ' ';
    }
  }
  else
  {
    out << "Ciclu negativ!";
  }

  return 0;
}