시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB104440.000%

문제

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).

예제 입력 1

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

예제 출력 1

0
100
41
1
11

예제 입력 2

2 0 2
1 2
1
2

예제 출력 2

0
Impossible

힌트

In the first sample, to get to the capital from the city $5$, we need to perform the following actions:

  • Buy a ticket with type $1$ for $10$ dollars and travel to the city $4$.
  • Buy a ticket with type $3$ for $1$ dollar and travel to the capital city $1$.

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.