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

using namespace std;

const int INF = 1e9;
const int N = 5e4 + 5;

struct edge {
  int to;
  int cost;
};

vector<edge> gr[N];
bool inq[N];
int nr[N];

int main() {
  ifstream cin("bellmanford.in");
  ofstream cout("bellmanford.out");
  int n, m;
  cin >> n >> m;
  while (m--) {
    int x, y, c;
    cin >> x >> y >> c;
    gr[x].push_back({y, c});
  }
  cin.close();
  vector<int> d(n + 1, INF);
  d[1] = 0;
  queue<int> q;
  q.push(1);
  inq[1] = true;
  bool ok = true;
  while (!q.empty() && ok) {
    auto nod = q.front();
    inq[nod] = false;
    q.pop();
    for (auto e: gr[nod]) {
      int cost = d[nod] + e.cost;
      if (cost < d[e.to]) {
        d[e.to] = cost;
        if (!inq[e.to]) {
          if (++nr[cost] > n - 1) {
            ok = false;
            break;
          }
          inq[e.to] = true;
          q.push(e.to);
        }
      }
    }
  }
  if (ok)
    for (int i = 2; i <= n; ++i)
      cout << d[i] << " ";
  else
    cout << "Ciclu negativ!\n";
  cout.close();
  return 0;
}