티켓

베를란드에는 $n$개의 도시가 있으며, 1번부터 $n$번까지 번호가 붙어 있다. 1번 도시는 베를란드의 수도이다. 도시들은 $n-1$개의 기차로 연결되어 있고, $i$번째 기차는 도시 $a_i$와 $b_i$를 잇는다. 기차 노선망 덕분에 어느 도시에서든 다른 모든 도시로 갈 수 있다. 여러 기차를 거쳐도 된다.

티켓은 $m$종류가 있다. $i$번째 종류는 도시 $v_i$에서 $w_i$베를란드 달러에 살 수 있다. 이 티켓으로 $v_i$에서 거리가 $k_i$ 이하인 임의의 도시 $x$로 이동할 수 있다. 거리는 이동에 쓴 기차의 수로 잰다.

어느 도시에서든 수도로 가는 최소 비용을 구하라.

첫 줄에 세 정수 $n$, $m$, $q$ ($1 \le n \le 10^5$, $0 \le m \le 10^5$, $1 \le q \le 10^5$)가 주어진다. 각각 도시 수, 티켓 종류 수, 질의 수이다.

다음 $n-1$개의 줄에는 $i$번째 기차가 잇는 두 도시 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n$)가 주어진다.

다음 $m$개의 줄에는 세 정수 $v_i$ ($1 \le v_i \le n$), 티켓을 사서 쓸 수 있는 도시, $k_i$ ($1 \le k_i \le n-1$), 티켓으로 이동할 수 있는 최대 거리, $w_i$ ($0 \le w_i \le 10^9$), 티켓 가격이 주어진다.

다음 $q$개의 줄에는 수도로 가는 비용을 구하려는 도시 $q_i$ ($1 \le q_i \le n$)가 주어진다.

각 질의마다 해당 도시에서 수도로 가는 최소 비용을 한 줄에 출력한다. 이 티켓들로 수도에 갈 수 없다면 <<Impossible>> (따옴표 제외)을 출력한다.

첫 번째 예제에서 도시 $5$에서 수도로 가려면 다음과 같이 한다.

• 1번 티켓을 10달러에 사서 도시 $4$로 이동한다.
• 3번 티켓을 1달러에 사서 수도인 도시 $1$로 이동한다.

1번 티켓으로 도시 $3$과 $2$로 갈 수도 있다. 도시 $5$에서 도시 $3$까지의 거리는 기차 1개, 도시 $2$까지는 기차 2개로 둘 다 2 이하이다. 그 뒤 2번이나 4번 티켓으로 수도에 갈 수 있지만, 이 경로는 훨씬 비싸다.