题目背景

小 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$		$k_i\leq 3$	$12$
$3$	$10^3$	迷宫为一条链	$9$
$4$		无	$16$
$5$	$10^5$	迷宫为一条链	$9$
$6$		迷宫为一个菊花图	$16$
$7$		无	$35$

对于 $100\%$ 的数据，$1\leq d,k_i\leq n\leq 10^5$，$1\leq v_i\leq 10^4$。

【Source】

Sweet Round 04$\ \$E

idea & std：Alex_Wei，验题：chenxia25