O. Короткий цикл через вершину

Как классная задача O, но цикл обязан проходить через вершину 1.

Динамика та же, меняется только место, куда смотрим: не вся диагональ, а одна её клетка $f_k[1][1]$.

Обратите внимание, что ответ может оказаться больше, чем в классной задаче: самый короткий отрицательный цикл в графе не обязан проходить через первую вершину, а иногда через неё вообще ни один не проходит.

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

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

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