도로망 축소

N개의 도시와 도시 간의 최단 거리가 주어진다. 모든 도시 쌍의 최단 거리를 보존하면서, 도로의 총 길이를 최소화하려 한다. 불필요한 도로를 제거한 후의 최소 도로 총길이를 구하시오.

두 도시 사이에 직접 연결된 도로가 없더라도 다른 도시를 경유하여 최단 거리가 유지된다면, 그 직접 도로는 제거할 수 있다.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 <= N <= 20)
둘째 줄부터 N개의 줄에 걸쳐 N x N 최단 거리 행렬이 주어진다. i번째 줄의 j번째 값은 도시 i에서 도시 j까지의 최단 거리를 의미한다. (1 <= 거리 <= 1000)

출력

불필요한 도로를 제거한 후의 최소 도로 총길이를 출력한다.

입출력 예시

입력 1

3
0 2 5
2 0 3
5 3 0

출력 1

5

입력 2

4
0 3 6 9
3 0 3 6
6 3 0 3
9 6 3 0

출력 2

9