3075번 - Astromeeting

때는 아주 먼 미래, 지구인은 태양계를 넘어 은하계를 넘나들 수 있는 시대를 맞이하게 되었다.

㈜유료도로당이라는 회사는 은하간에 초광속터널을 제공하여 은하간에 편리하고 빠르게 이동할 수 있게 하였다. 이때 다른 은하로 여행하기 위해 ㈜유료도로당에 제공해야 할 경비는 은하에서 다른 은하로 가는 총 경로의 길이 d의 제곱이다. 즉, 어느 은하에서 다른 은하로 가는 총 경로의 길이가 1이라면, ㈜유료도로당에 내야 할 돈은 1² = 1원이고, 길이가 7이라면, 내야 할 돈은 7² = 49원이다. ㈜유료도로당은 여러 경유지를 거쳐 다른 은하에 도착하였다고 해도, 최초의 지점부터 도착 지점 사이의 거리를 기준으로 비용을 정한다.

안드로메다 은하에 살고 있는 슬기는 소혹성 B-612호에 있는 지성에게 미팅을 해달라고 요청하였다. 이 요청을 흔쾌히 수락한 지성은 M31은하에 있는 친구와 슬기를 미팅을 시켜주기로 하였다. 하지만 세 명이 어디에서 모일지 결정하는 것은 쉬운 일이 아니었다. 서로에게 먼 곳의 은하에서 만나게 된다면, 괜히 교통비만 비싸지기 때문에 모두가 만족할 만한 장소에서 만나야 할 필요가 생긴 것이었다.

위와 같이 은하가 너무나 많이 존재하여 어디에서 만나는 것이 최저의 지출을 하게 되는지 모르는 사람들을 위하여 n명의 사람이 각각 자신의 은하에서 미팅 장소까지 가는 교통비의 합을 최소로 하는 은하를 찾고, 그 비용을 구하여라. (모든 사람은 미팅 장소에 도달할 수 있어야 하며, 답은 유일하게 존재한다고 가정한다.)

위의 그림에서는 1, 5번 은하에 있는 사람이 서로 만난다고 한다면, 4번 은하에서 만날 때 (2+1)² + (1+2)² = 18원이 지출되므로 비용이 가장 적게 들어간다.

입력은 총 T (1 ≤ T ≤ 100)개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 T가 주어진다.

각각의 테스트 케이스의 첫째 줄에는 서로 미팅을 하고자 하는 사람의 수 n (2 ≤ n ≤ 100), 은하의 수 p (2 ≤ p ≤ 100), 그리고 은하간의 길의 개수 q (1 ≤ q ≤ 100)가 주어진다. 그 다음 n줄에는 각각 미팅을 하는 사람들의 현재 있는 은하의 번호들이 주어진다. 여기서 은하의 번호는 1부터 차례대로 부여된다고 가정한다. 즉, p가 50이라면 1~50의 번호가 붙여진 은하가 존재한다. 그 다음 q줄에는 i j d가 주어지는데 각 i, j (1 ≤ i, j ≤ p)는 은하의 번호이고 d (0 ≤ d ≤ 100의 정수)은 은하간의 거리를 의미한다.

가장 가까운 은하의 번호와 그때의 총비용을 출력하라.