뉘른베르크로 이사하기

대중교통은 현대 도시 생활에서 가장 중요한 발명품 중 하나이지만, 우리는 평소 그 사실을 잘 의식하지 못한다. 대중교통 덕분에 도시 안에서의 이동이 훨씬 편해지지만, 그래도 우리는 지하철에서 보내는 시간을 되도록 줄이고 싶어 한다.

NWERC 2009를 겪은 뒤로 뉘른베르크는 당신의 마음속에서 특별한 도시가 되었고, 몇 년 뒤 당신은 이곳으로 이사하기로 한다. 유일한 고민은 도시의 어느 지역에 살지 정하는 것이다. 당신은 정기적으로 다니는 곳들을 오갈 때 지하철에서 보내는 시간이 최소가 되는 곳에 살고 싶다.

당신은 정기적으로 방문할 모든 장소(직장, 친구 집, 가끔 가는 크리스마스 마켓 등)와 각 장소를 일 년에 몇 번 갈 것으로 예상하는지를 적어 두었다. 당신은 항상 집에서 어떤 장소로 갔다가 다시 집으로 돌아온다. 예를 들어 퇴근 후에 어딘가에 간다면, 두 목적지를 곧바로 잇는 대신 먼저 집에 들렀다가 다시 출발한다. 목표는 일 년 동안의 총 이동 시간이 최소가 되는 역을 고르는 것이다.

당신은 항상 지하철을 이용하며, 뉘른베르크의 지하철망은 트리 모양이므로 임의의 두 역 사이에는 정확히 하나의 경로만 존재한다.

수식으로 나타내면, 두 역 $h$와 $a$ 사이의 유일한 경로를 따라가는 이동 시간을 $d(h, a)$라 하자. 당신이 역 $h$에 살면서 역 $a_i$를 일 년에 $f_i$번 방문한다면, 각 방문은 왕복이므로 일 년 동안의 총 이동 시간은 $\sum_i 2 f_i \, d(h, a_i)$이다. 이 총합의 최솟값과 그 값을 달성하는 모든 역을 구하라.

첫째 줄에 테스트 케이스의 수 $c$ ($1 \le c \le 200$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

각 테스트 케이스의 첫째 줄에는 지하철역의 수 $n$ ($1 \le n \le 50000$)이 주어진다. 이어지는 $n - 1$개의 줄에는 각각 세 정수 $a$, $b$, $t$ ($1 \le a, b \le n$, $1 \le t \le 300$)가 주어진다. 이는 역 $a$와 역 $b$가 직접 연결되어 있으며 두 역 사이를 이동하는 데 $t$초가 걸린다는 뜻이다. 이 간선들은 항상 트리를 이룬다.

그다음 줄에는 정기적으로 방문하려는 역의 수 $m$ ($0 \le m \le n$)이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $a$와 $f$ ($1 \le a \le n$, $1 \le f \le 500$)가 주어진다. 이는 역 $a$를 일 년에 총 $f$번 방문하려 한다는 뜻이다. 어떤 역도 이 목록에 두 번 이상 나타나지 않는다.

각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄에는 최적의 역에 살 때 일 년 동안 이동에 쓰는 총 시간(초)을 출력한다. 둘째 줄에는 이 최솟값을 달성하는 모든 역을 오름차순으로 공백 하나로 구분하여 출력한다.