O. Самый короткий отрицательный цикл

Найдите наименьшее количество рёбер в цикле отрицательного веса.

Форд — Беллман отвечает на вопрос «есть ли такой цикл», но про его длину ничего не говорит. Нужна другая динамика — по числу рёбер.

Пусть $f_k[i][j]$ — наименьший вес маршрута из $i$ в $j$ ровно из $k$ рёбер (вершины могут повторяться). Тогда

а отрицательный цикл из $k$ рёбер существует тогда и только тогда, когда $f_k[i][i] < 0$ для какого-нибудь $i$.

Перебираем $k$ от 1 до $n$ и отвечаем на первом же, где нашлось. Дальше $n$ идти незачем: цикл минимальной длины не повторяет вершин, значит рёбер в нём не больше $n$.

Стоимость одного шага — $O(n^3)$, всего $O(n^4)$. При $n \le 60$ это тринадцать миллионов операций.

Заметьте, что маршрут из $k$ рёбер с повторами — это нормально: если он замкнут и имеет отрицательный вес, внутри него обязательно найдётся отрицательный простой цикл, и он не длиннее. Поэтому наименьшее $k$, на котором диагональ ушла в минус, и есть ответ.

Первая строка содержит числа $n$ ($1 \le n \le 60$) и $m$ ($0 \le m \le 2000$).

Далее идут $m$ строк с рёбрами: начало, конец и вес ($|w| \le 1000$). Возможны кратные рёбра и петли.

Одно число — наименьшее количество рёбер в отрицательном цикле, или $-1$, если такого цикла нет.