| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 12 | 5 | 5 | 41.667% |
There are $n$ cities in Berland, which are enumerated from 1ドル$ to $n$. City number 1ドル$ is a capital of Berland. Cities are connected by $n-1$ trains, $i$-th of them connects city $a_i$ with city $b_i$. Berland train system allows you to get from every city to any other, possibly, using more than one train.
There are $m$ types of the tickets: $i$-th of them can be bought in city $v_i$ for $w_i$ berland dollars and allows to travel from $v_i$ to any city $x$ such that the distance from $v_i$ to $x$ is less or equal to $k_i$. The distance is measured in trains used during the travel.
Your task is to find minimal cost to get from some cities to capital.
In the first line you are given three integers $n,ドル $m,ドル $q$ (1ドル \le n \le 10^5,ドル 0ドル \le m \le 10^5,ドル 1ドル \le q \le 10^5$) -- number of cities in Berland, number of different type of tickets, number of queries correspondingly.
Each of next $n - 1$ lines contain integers $a_i$ and $b_i$ (1ドル \le a_i, b_i \le n$) -- cities connected by $i$-th train.
In the next $m$ lines types of tickets are described: $i^{th}$ contains three integers $v_i$ (1ドル \le v_i \le n$) -- city where one could buy and use it, $k_i$ (1ドル \le k_i \le n - 1$) -- maximum distance one could travel using this ticket, $w_i$ (0ドル \le w_i \le 10^9$) -- price of the ticket.
In the next $q$ lines are described queries: $i^{th}$ of them contains integer $q_i$ (1ドル \le q_i \le n$) -- city, from which you want to calculate cost to get to capital.
For every query output single line with integer -- required cost to get from city to capital. If it's impossible to get to the capital using such tickets, print <<Impossible>> (without quotes).
5 4 5 1 2 2 3 3 4 3 5 5 2 10 3 1 40 4 3 1 2 1 100 1 2 3 4 5
0 100 41 1 11
2 0 2 1 2 1 2
0 Impossible
In the first sample, to get to the capital from the city 5ドル,ドル we need to perform the following actions:
Note that it's also possible to travel to the cities 3ドル$ and 2ドル$ using a ticket with type 1ドル$ (the distance between 5ドル$ and 3ドル$ is one train, while the distance between 5ドル$ and 2ドル$ is two trains, which is less or equal to 2ドル$), and get to the capital using tickets 2ドル$ or 4ドル,ドル but it would be a lot more expensive to travel to the capital this way.