「SWTR-4」Collecting Coins

小 A 喜欢 Collecting Coins。他还有个好朋友叫做小 c。 小 c 在外出游玩的时候被困在了一个迷宫里面，小 A 得知消息后，立刻放下了自己手中正在打的树套树套树套树，出发去营救她。

经过一番勘察，小 A 发现小 c 被困的迷宫由 $n$ 个房间组成，这些房间用 $n-1$ 扇门连接，**形成了一颗树**。小 c 被困在 $d$ 号房间。 小 A 还发现每扇门上都写有一个数字 $v$，经过该扇门就会获得 $v$ 个金币，但每扇门上的金币只能获得一次。 由于把小 c 困在迷宫里的坏人早已知道小 A 会来救她，所以他们在每个房间里都布下了陷阱，使得第 $i$ 个房间最多可以进入 $k_i$ 次，否则小 A 也会被困在迷宫里。Luckily，小 c 在向小 A 求救的时候，已经将这个陷阱告诉了他。 小 A 在进入迷宫的时候可以任选初始房间 $r$（进入迷宫算一次进入房间 $r$）。**小 A 可以离开迷宫，当且仅当他在房间 $r$。** 如果小 A 进入了 $d$ 号房间，我们就认为他成功地救下了小 c。在救下小 c 后，小 A 还可以带着她继续在迷宫中行动。 虽然小 A 并不是一个非常贪财的人，但还是想知道：在**成功救下小 c** 且离开迷宫的前提下，他最多能获得多少金币。

第一行，两个整数 $n,d$ —— 表示房间个数和小 c 被困的房间号。 接下来 $n-1$ 行，每行三个整数 $x_i,y_i,v_i$ —— 分别表示第 $i$ 扇门连接的两个房间编号和这扇门上写的数。 接下来一行，$n$ 个整数 $k_1,k_2,\cdots,k_n$ —— 表示每个房间最多可进入的次数。

一行一个整数，表示小 A 能获得的金币数量的最大值。

6 4
1 2 3
2 3 4
2 4 5
3 5 2
3 6 3
1 2 1 1 2 2

5

6 4
1 2 3
2 3 4
2 4 5
3 5 2
3 6 3
1 1 1 1 1 1

0

6 4
1 2 3
2 3 4
2 4 5
3 5 2
3 6 3
2 2 2 2 2 2

12

12 6
1 4 33
2 11 51
3 9 100
4 8 7
5 9 35
6 12 30
7 11 58
8 10 65
9 10 59
10 12 9
11 12 72
2 2 2 3 2 1 2 1 2 3 2 2

263

【样例 $1$ 说明】  一种最优的走法为：$2\to 4\to 2$，共可获得 $5$ 金币。 【样例 $2$ 说明】 如上图，小 A 只能空降到 $4$ 号房间，然后再离开迷宫，共可获得 $0$ 金币。 【样例 $4$ 说明】  一种最优的走法为：$3\to 9\to 10\to 8\to 10\to 12\to 6\to 12\to 10\to 9\to 3$，共可获得 $100+59+65+9+30=263$ 金币。 【数据范围与约定】 **本题使用捆绑测试。** Subtask 编号 | $n\leq$ | 特殊性质 | 分值 | :-: | :-: | :-: | :-: | $1$ | $12$ | $k_i=1$ | $3$ | $2$ | $12$ | $k_i\leq 3$ | $12$ | $3$ | $10^3$ | 迷宫为一条链 | $9$ | $4$ | $10^3$ | 无 | $16$ | $5$ | $10^5$ | 迷宫为一条链 | $9$ | $6$ | $10^5$ | 迷宫为一个菊花图 | $16$ | $7$ | $10^5$ | 无 | $35$ | 对于 $100\%$ 的数据，$1\leq d,k_i\leq n\leq 10^5$，$1\leq v_i\leq 10^4$。 【Source】 [Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $E idea & std：[Alex_Wei](https://www.luogu.com.cn/user/123294)，验题：[chenxia25](https://www.luogu.com.cn/user/138400)