С помощью алгоритма Форда-Беллмана найдем n-ю и 2n-ю строки матрицы и массив d. Сравним a_n,i с a_2n,i. Если они не равны, то выведем с помощью массива d цикл отрицательного веса (в d для вершин этого цикла будут записаны как раз предыдущие в нем). В этой задаче удобно считать, что бесконечности тоже уменьшаются.