收集签名

Problem Description

在荒野乱斗的世界中共有 $n$ 座城市，由 $n-1$ 条长短不一的双向道路连通。 收集狂科莱特在 $1$ 号城市中的礼物店内工作。为了收集她最爱的英雄们的签名，她希望开始一段从 $1$ 号城市开始，经过每个城市至少一次，并最后回到 $1$ 号城市的旅程。她的移动速度为 $1$ 米每秒。 除了缓慢地行走外，她也可以使用她的超级技能来收集签名。具体来说，假设她现在处于 $x$ 号城市，她使用超级技能的过程如下：

1. 选择一个终止城市 $y$。
2. 从城市 $x$ 冲刺到城市 $y$，收集沿途所有城市中英雄的签名，再从城市 $y$ 冲刺回城市 $x$。
3. 使用超级技能经过每条道路的所需的时间为 $k$ 秒，无视道路的长度。 她只能在一些特殊的城市中使用超级技能，且每个特殊城市至多发动一次。你能告诉她整个旅程所需的最小时间吗？

Input

输入的第一行包含一个整数 $T$ ($1 \le T \le 4 \times 10^3$) ------ 表示该组数据包含的测试点组数。 对于每组测试点, 输入的第一行包含 $n$, $k$ ($1 \le n \le 4 \times 10^3, 1 \le k \le 10^9$)，表示城市的数量以及使用超级技能经过一条道路所需的时间。 输入的第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$ ($b_i \in \{0,1\}$)，表示科莱特能在某个城市发动超级技能的次数。 接下来 $n-1$ 行每行包含三个整数 $x_i$, $y_i$, $w_i$ ($1 \le x_i,y_i \le n, 1 \le w_i \le 10^9$)，表示第 $i$ 条道路的长度为 $w_i$ 米，连接的城市为 $x_i$ 号城市与 $y_i$ 号城市。 保证所有测试点的 $\sum n$ 之和小于等于 $2\times10^4$。

Output

对于每组测试点，输出一行一个整数，表示科莱特旅途所需的最短时间。

Sample Input

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

Sample Output

6
14

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）