도로변 광고
시간 제한1초메모리 제한512 MB
가중치가 있는 트리에서 서로 다른 다섯 정점이 주어지는 질의 Q개에 대해, 다섯 정점 중 두 개를 잇는 최단 경로 위에 놓이는 모든 간선의 가중치 합을 구한다.
문제
Singapore National Olympiad in Informatics (SG NOI)는 2017년에 20번째 대회를 연다. 올해는 다섯 개의 후원사가 있다 (알파벳 순): Garena, IMDA, Lee Foundation, Micron, 그리고 주최 겸 후원 기관인 School of Computing (SoC).
SG NOI 의장인 Tan Sun Teck 부교수는 이 다섯 후원사를 잇는 도로에 도로변 광고를 붙이려 한다. 그는 SG NOI와 관련된 사람이 자신의 사무실 사이를 이동할 때마다 (예를 들어 중요한 주간 NOI 회의를 위해) 지나는 모든 도로에서 SG NOI 관련 광고를 보게 하고 싶다. 따라서 다섯 후원사 중 어느 두 곳을 잇는 최단 경로 위의 모든 도로에는 도로변 광고가 설치되어야 한다.
싱가포르의 각 도로마다 광고를 설치하는 비용은 미리 알려져 있다. 이 광고 캠페인의 전체 비용은 그 비용들의 합이다. Tan 교수는 목표를 달성하는 데 필요한 최소 비용을 구하려 한다.
참고로 이 버전의 싱가포르에서 도로들은 흥미로운 성질을 가진다. 싱가포르의 임의의 두 지점 사이에는 정확히 하나의 경로만 존재한다.
입력
입력의 첫째 줄에는 양의 정수 V가 주어진다.
다음 V − 1개 줄에는 각각 3개의 정수 u, v, w가 주어지며, 이는 싱가포르의 지점 u와 지점 v가 도로로 연결되어 있고 그 도로에 도로변 광고를 설치하는 비용이 w SGD임을 뜻한다.
0 ≤ u, v < V이고 1 ≤ w ≤ 1 000임이 보장된다.
그다음 줄에는 양의 정수 Q가 주어지며, 이는 질의의 수를 나타낸다. 이후 Q개 줄에는 각각 5개의 정수가 주어지며, SG NOI의 다섯 후원사 위치인 지점 {a, b, c, d, e}를 나타낸다.
a, b, c, d, e는 서로 다름이 보장된다.
출력
각 질의마다 프로그램은 Tan 교수의 도로변 광고 캠페인에 필요한 최소 비용을 나타내는 정수 하나를 표준 출력에 한 줄로 출력해야 한다.
제한
- 5 ≤ V ≤ 50 000
- 1 ≤ Q ≤ 10 000