N. Сколько обменов в выгодной цепочке

Как классная задача N, но выведите наименьшее количество обменов в выгодной цепочке.

Сведение то же: вес ребра равен $-a$, выгодная цепочка — отрицательный цикл. Меняется вопрос: нужен не факт существования, а длина самого короткого такого цикла.

Считается динамикой по числу рёбер, как в классной задаче O: $f_k[i][i] < 0$ для наименьшего $k$ и есть ответ.

Обмен валюты на саму себя с положительным показателем — цепочка из одного обмена, и это законный ответ.

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

Далее идут $m$ строк: валюта $u$, валюта $v$ и показатель $a$ ($|a| \le 1000$).

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