По данным из неизвестных источников, в древние времена в Азербайджане было N городов. Между некоторыми из этих городов проходили двухсторонние дороги. По находкам археолога Барыша, стало известно, что из любого из этих N городов было возможно путешествовать в любой другой (прямого пути между нимимогло и не быть).
К сожалению, информация о прямых путях между городами и длинами этих путей была потеряна, но Барыш продолжил свои исследования обнаружив кратчайшие пути между всеми городами и построил соответствующую таблицу A размеров N × N . В этой таблице число A[ij]
означает кратчайший путь между городами i и j .
Основываясь на полученных данных, помогите Барышу понять могли ли существовать N таких городов. Если это возможно, найдите минимальную сумму длин всех дорог.
В первой строке одно целое число N (1
≤ N ≤ 200
) – количество городов, далее следует N строк по N чисел в каждой, где A[ij]
(1
≤ A[ij]
≤ 10^9
(i≠j)
, A[ii] = 0
) – длина кратчайшего пути между городами i и j .
В случае если невозможно найти N городов, выведите "-1". В противном случае выведите минимальную возможную сумму длин всех дорог.