E. Вес найденного цикла

Как классная задача E, но выводится не сам цикл, а его вес.

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

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

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

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

Далее идут $n$ строк по $n$ чисел — матрица смежности. Веса по модулю меньше $10^5$; значение ровно $10^5$ означает отсутствие ребра.

Одно число — вес найденного цикла, или NO, если отрицательного цикла нет.