#include <algorithm>
#include <iostream>
#include <vector>

const int INF = 1000000000;

struct edge {
  int from;
  int to;
  int cost;
};

int n; // Кол-во вершин
int e; // Кол-во рёбер
std::vector<edge> gr(e);
/* Ввод графа */

void FordBellman(int start) {
  std::vector<int> d(n, INF); // Цены пути
  std::vector<int> p(n, -1);  // Предки вершин
  d[start] = 0;
  int x;
  for (int i = 0; i < n;
       ++i) { // Выполняем n раз, чтобы найти отрицательный цикл
    for (int j = 0; j < e; ++j) {
      if (d[gr[j].from] < INF) {
        if (d[gr[j].to] > d[gr[j].from] + gr[j].cost) {
          d[gr[j].to] = d[gr[j].from] + gr[j].cost;
          // если есть отрицательный цикл, чтобы не ушли за границы инта
          d[gr[j].to] = std::max(d[gr[j].to], -INF);
          p[gr[j].to] = gr[j].from;
          x = gr[j].to; // Запоминаем последнее сделанное изменение
        }
      }
    }
    if (x == -1) { // Не было сделано ни одного изменения - дальнейшие итерации
                   // бессмысленны
      break;
    }
  }

  if (x == -1) {
    // На последней фазе не было изменений - нет отрицательных циклов
    std::cout << "No negative cycles" << std::endl;
  } else {
    std::vector<int> path;
    int y = x; // x - либо лежит на отрицательном цикле, либо достижима из него
    for (int i = 0; i < n; ++i) {
      y = p[y];
    } // y - точно лежит на цикле
    std::vector<int> negcycle;
    for (int cur = y;; cur = p[cur]) {
      path.push_back(cur);
      if (cur == y && path.size() > 1) {
        break;
      }
    }
    std::reverse(path.begin(), path.end());
    std::cout << "Negative cycle" << std::endl;
    for (int i = 0; i < path.size(); ++i) {
      std::cout << path[i] << " ";
    }
    std::cout << std::endl;
  }
}