题目描述
小明住在 H 国的首都。H 国有 $n$ 个城市，其中 $1$ 号城市为其首都。城市间有 $n-1$ 条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都，从任何一个城市走到首都的路径是 **唯一** 的。
想要通过某一条道路，你必须使用一次过路券。H 国一共有 $m$ 种过 路券，每张过路券以三个整数表示：$v\ k\ w$：你可以在城市 $v$ 以价格 $w$ 买到一张过路券。这张券可以使用 $k$ 次。这意味着，拿着这张券通过了 $k$ 条道路之后，这张券就不能再使用了。
请注意你同一时间最多只能拥有 **最多一张** 过路券。但你可以随时撕掉手中已有的过路券， 并且在所在的城市再买一张。 小明家在首都。他有 $q$ 位朋友，他希望把这些朋友们都邀请到他家做客。他想要知道每位朋友要花多少路费。他的朋友们永远都会选择一条花费最少的方式到达首都。
小明没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？
输入
输入的第一行包含两个空格隔开的整数 $n$ 和 $m$，表示 H 国的城市数量和过路券的种数。
之后的 $n-1$ 行各自包含两个数 $a_i$ 和 $b_i$，代表城市 $a_i$ 到城市 $b_i$ 间有一条单向道路。
之后的 $m$ 行每行包括三个整数 $v_i,k_i$ 和 $w_i$，表示一种过路券。
下一行包含一个整数 $q$，表示小明朋友的数量。
之后的 $q$ 行各自包含一个整数，表示小明朋友所在的城市。
输出
输出共 $q$ 行，每一行代表一位朋友的路费。
样例输入输出
输入#1
复制
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
提示
【样例解释】
对于第一位朋友，他在 $5$ 号城市只能购买一种过路券，花费 $10$ 元并且可以使用 $3$ 次。这 足够他走到首都，因此总花费是 $10$元。
对于第二位朋友，他在 $6$ 号城市只能购买 $20$ 元的过路券，并且只能使用一次。之后，他可以在 $3$ 号城市购买 $2$ 元，可以使用 $3$ 次的过路券走到首都。总花费是 $22$ 元。
对于第三位朋友，他在 $7$ 号城市可以购买两种过路券。他可以花 $3$ 元买一张可以使用 $2$ 次的券，然后在 $3$ 号城市再买一张 $2$ 元，可以使用 $3$ 次的券，走到首都。总花费是 $5$ 元，而且其他的购买方式不会比这种更省钱。
【数据范围】
对于 $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$。