은하 미팅

먼 미래에는 여러 은하 사이를 터널과 길로 이동할 수 있다. 한 사람이 자신의 은하에서 다른 은하로 이동할 때 사용하는 최단 경로의 총 길이를 d라고 하면, 그 사람이 내야 하는 교통비는 d^2원이다. 여러 은하를 거쳐 이동하더라도 비용은 출발 은하에서 도착 은하까지의 최단 이동 거리만으로 정해진다.

n명의 사람이 각자의 은하에서 하나의 미팅 장소로 이동하려고 한다. 모든 사람이 도달할 수 있는 은하 중에서, 각 사람이 그 은하까지 이동하는 교통비의 합이 최소가 되는 은하를 찾아야 한다. 즉, 사람 i의 현재 은하에서 후보 은하까지의 최단 거리를 dist_i라고 할 때, sum(dist_i^2)를 최소로 하는 은하 번호와 그때의 총비용을 구하라.

모든 사람이 도달할 수 있는 미팅 장소가 적어도 하나 존재하며, 답은 유일하다고 가정한다.

입력은 여러 테스트 케이스로 이루어진다.

첫 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 100)

각 테스트 케이스의 첫 줄에는 미팅에 참여하는 사람의 수 n, 은하의 수 p, 은하 사이의 길의 수 q가 주어진다. (2 <= n <= 100, 2 <= p <= 100, 1 <= q <= 100)

다음 n개의 줄에는 각 사람이 현재 있는 은하 번호가 하나씩 주어진다. 은하 번호는 1부터 p까지이다.

다음 q개의 줄에는 세 정수 i, j, d가 주어진다. 이는 은하 i와 은하 j를 잇는 양방향 길의 길이가 d임을 뜻한다. (1 <= i, j <= p, 0 <= d <= 100)

각 테스트 케이스마다 총비용이 최소가 되는 은하 번호와 그때의 총비용을 한 줄에 출력한다.