시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

Singapore National Olympiad in Informatics (SG NOI) celebrates its 20-th version in year 2017 (this year). This year, we are grateful to have FIVE (5) different sponsors (in alphabetical order): Garena, IMDA, Lee Foundation, Micron, and the organizer+sponsor: School of Computing (SoC).

For each road in Singapore, the cost of putting an advertisement on that road is known in advance. The overall cost of this advertising campaign is the sum of these costs. Prof Tan wants to find the minimum cost required to achieve his objective.

By the way, the roads in this version of Singapore have an interesting property where there is exactly one possible path between any two landmarks in Singapore.

## 입력

The first line of input contains one positive integer V.

The next V − 1 lines of input will each contain 3 integers: u, v, w that denotes that landmark u and landmark v in Singapore are connected with a road and installing a roadside advert in this road costs w SGD.

It is guaranteed that 0 ≤ u, v < V and 1 ≤ w ≤ 1 000.

Then, there will be another line with one positive integer Q, denoting the number of queries. Afterwards, there will be Q lines with 5 integers each, denoting the location of the 5 sponsors of SG NOI: landmarks {a, b, c, d, e}.

It is guaranteed that a, b, c, d and e are pairwise different.

## 출력

For each query, your program must output one line with a single integer to standard output: the minimum cost for Prof Tan’s roadside advertisement campaign.

## 제한

• 5 ≤ V ≤ 50 000
• 1 ≤ Q ≤ 10 000

5
0 1 1
1 2 2
2 3 3
3 4 4
1
4 0 3 1 2

10

6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5

## 예제 출력 2

21
16

Figure 2: An example map with 15 towns and 19 roads.