#include <bits/stdc++.h>

using namespace std;

#define inf INT_MAX

int N, M;
vector<int> dist;
vector<pair<int, pair<int, int>>> muchii;

void bellman_ford(int n, int m, int s) {
  dist.assign(n + 1, inf);
  dist[s] = 0;
  for (int i = 1; i < n; ++i) {
    for (auto m : muchii) {
      int x = m.first;
      int y = m.second.first;
      int w = m.second.second;
      if (dist[y] > dist[x] + w) {
        dist[y] = dist[x] + w;
      }
    }
  }
  bool hellNah = false;
  for (auto m : muchii) {
      int x = m.first;
      int y = m.second.first;
      int w = m.second.second;
      if (dist[y] > dist[x] + w) {
        hellNah = true;
        break;
      }
  }
  if (hellNah) {
    cout << "Ciclu negativ!";
  }
  else {
    for (int i = 2; i <= n; ++i) {
      cout << dist[i];
    }
  }
}

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  cin >> N >> M;
  for (int i = 1; i <= M; ++i) {
    int x, y, cost;
    cin >> x >> y >> cost;
    muchii.push_back({x, {y, cost}});
  }
  bellman_ford(N, M, 1);
  return 0;
}