当前没有测试数据。

3.小明聚会

题目描述

小明住在$H$国的首都。$H$国有$n$个城市，其中$1$号城市为其首都。城市间有$n-1$条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都，从任何一个城市走到首都的路径是唯一的。

想要通过某一条道路，你必须使用一次过路券。$H$国一共有$m$种过路券，每张过路券以三个整数表示：$v$ $k$ $w$：你可以在城市$v$以价格$w$买到一张过路券。这张券可以使用$k$次。这意味着，拿着这张券通过了$k$条道路之后，这张券就不能再使用了。

请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。小明家在首都。他有$q$位朋友，他希望把这些朋友们都邀请到他家做客。他想要知道每位朋友要花多少路费。他的朋友们永远都会选择一条花费最少的方式到达首都。

小明没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？

输入格式

输入的第一行包含两个空格隔开的整数$n$和$m$，表示$H$国的城市数量和过路券的种数。

之后的$n-1$行各自包含两个数$a$和$b$，代表城市$a$到城市$b$间有一条单向道路。

之后的$m$行每行包括三个整数$v$，$k$和$w$，表示一种过路券。

下一行包含一个整数$q$，表示小明朋友的数量。

之后的$q$行各自包含一个整数，表示小明朋友所在的城市。

输出格式

输出共$q$行，每一行代表一位朋友的路费。

数据范围与提示

• 对于$40\%$的数据：$n$，$m$，$q \leq 10$，$w_i \leq 10$；
• 另有$20\%$的数据：$n$，$m$，$q \leq 500$，$w_i \leq 100$；
• 另有$20\%$的数据：$n$，$m$，$q \leq 5 \times 10^{3}$，$w_i \leq 10^{3}$；
• 对于$100\%$的数据：$1 \leq n$，$m$，$q \leq 10^{5}$，$1 \leq w_i \leq 10^{4}$，$1 \leq v_i$，$k_i \leq n$。

样例

7 7 
3 1 
2 1 
7 6 
6 3 
5 3 
4 3 
7 2 3
7 1 1 
2 3 5
3 6 2
4 2 4 
5 3 10 
6 1 20 
3 
5 
6 
7 

10 
22 
5

说明

对于第一位朋友，他在$5$号城市只能购买一种过路券，花费$10$元并且可以使用$3$次。这足够他走到首都，因此总花费是$10$元。

对于第二位朋友，他在$6$号城市只能购买$20$元的过路券，并且只能使用一次。之后，他可以在$3$号城市购买$2$元，可以使用$3$次的过路券走到首都。总花费是$22$元。

对于第三位朋友，他在$7$号城市可以购买两种过路券。他可以花$3$元买一张可以使用$2$次的券，然后在$3$号城市再买一张$2$元，可以使用$3$次的券，走到首都。总花费是$5$元，而且其他的购买方式不会比这种更省钱。