일곱 왕국의 전령

일곱 왕국에 또 문제가 생겼다. 로버트 바라테온 왕에게 용이 나타났다는 소문이 들어왔다. 왕은 나라 안의 $n$개 도시 모두에 가능한 한 빨리 위험을 알리려 한다. 그런데 왕자 조프리가 새총으로 비둘기를 거의 다 쏘아 떨어뜨렸다. 한 마리만 남았다. 왕은 이 전령을 보낼 도시 하나를 골라, 나머지 도시를 모두 도는 데 걸리는 시간을 최소로 하려 한다.

일곱 왕국의 전령은 매우 게으르다. 도시를 도는 경로를 미리 짜지 않는다. 대신 다음 방식을 고수한다.

전령이 도시 $i$에 있고, 지금까지 방문한 도시의 집합을 $M$이라 하자. 다음에 갈 도시 $j$는 $M$에 속하지 않은 도시 가운데 $i$에서 가장 가까운 도시이다. 가장 가까운 도시가 여럿이면 번호가 가장 작은 도시로 간다.

도시는 평면 위의 점이며, 직교 좌표 $(x_i, y_i)$로 주어진다. 두 도시 사이를 이동하는 데 드는 거리와 시간은 두 점 사이 유클리드 거리의 제곱이다.

로버트 왕이 전령이 나머지 모든 도시를 방문하는 총 시간이 가장 짧아지도록 출발 도시를 고르도록 도와라.

첫 줄에 도시의 개수 $n$ ($2 \le n \le 300$)이 주어진다. 다음 $n$개 줄에는 각 도시의 좌표 $x_i$와 $y_i$가 주어진다 ($-300 \le x_i, y_i \le 300$).

모든 도시에 알리는 데 걸리는 최소 시간을 한 줄에 출력한다.