민호의 궁금증

강호는 N개의 도시로 이루어진 나라에 살고 있다. 도시들은 도로로 연결되어 있고, 각 도로에는 이동 시간이 있다. 도로망은 연결되어 있어 어떤 두 도시 사이도 이동할 수 있다.

도시 A에서 도시 B로 직접 연결된 도로를 이용하거나 여러 도시를 거쳐 이동할 수 있으면, 도시 A에서 도시 B로 갈 수 있다고 한다.

강호는 모든 도시 쌍에 대해 최단 이동 시간 표를 만들었다. 민호는 이 표만 보고, 같은 최단 이동 시간 표를 만들 수 있는 원래 도로망 중 도로 개수가 최소인 경우를 찾으려고 한다.

모든 도시 쌍 사이에 표의 값과 같은 시간의 도로를 하나씩 두면 같은 표를 만들 수 있다. 그러나 이 방법이 도로 수를 최소로 만든다고는 할 수 없다. 어떤 두 도시 사이의 이동 시간이 다른 도시들을 거쳐 가는 이동 시간과 정확히 같다면, 그 직접 도로를 제거해도 모든 도시 쌍의 최단 이동 시간은 변하지 않는다.

모든 도시 쌍의 최단 이동 시간이 주어졌을 때, 도로 개수가 최소인 도로망에서 모든 도로의 이동 시간 합을 구하는 프로그램을 작성하시오. 그런 도로망이 존재할 수 없다면 -1을 출력한다.

첫째 줄에 도시의 개수 N (1 <= N <= 20)이 주어진다.

둘째 줄부터 N개의 줄에 각각 N개의 정수가 주어지며, 도시 사이를 이동하는 데 필요한 시간을 나타낸다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 같은 도시 사이의 시간은 0이고, 서로 다른 도시 사이의 시간은 2500 이하의 자연수이다.

첫째 줄에 도로 개수가 최소일 때 모든 도로의 이동 시간 합을 출력한다. 불가능한 경우에는 -1을 출력한다.