在荒野乱斗的世界中共有 $n$ 座城市，由 $n−1$ 条长短不一的双向道路连通。

收集狂科莱特在 $1$ 号城市中的礼物店内工作。为了收集她最爱的英雄们的签名，她希望开始一段从 $1$ 号城市开始，经过每个城市至少一次，并最后回到 $1$ 号城市的旅程。她的移动速度为 $1$ 米每秒。

除了缓慢地行走外，她也可以使用她的超级技能来收集签名。具体来说，假设她现在处于 $x$ 号城市，她使用超级技能的过程如下：

• 选择一个终止城市 $y$。

• 从城市 $x$ 冲刺到城市 $y$，收集沿途所有城市中英雄的签名，再从城市 $y$ 冲刺回城市 $x$。

• 使用超级技能经过每条道路的所需的时间为 $k$ 秒，无视道路的长度。

她只能在一些特殊的城市中使用超级技能，且每个特殊城市至多发动一次。你能告诉她整个旅程所需的最小时间吗？

输入的第一行包含一个整数 $T (1≤T≤4×10^3 ) ------ 表示该组数据包含的测试点组数。

对于每组测试点,

输入的第一行包含 $n,k (1≤n≤4×10^3 ,1≤k≤10^9 )$，表示城市的数量以及使用超级技能经过一条道路所需的时间。

输入的第二行包含 $n$ 个整数 $b_1,b_2,…,b_n (b_i ∈0,1)$，表示科莱特能在某个城市发动超级技能的次数。

接下来 $n−1$ 行每行包含三个整数 $x_i,y_i,w_i (1≤x_i,y_i≤n,1≤w_i≤10^9 )$，表示第 $i$ 条道路的长度为 $w_i$ 米，连接的城市为 $x_i$ 号城市与$y_i$ 号城市。

保证所有测试点的 $∑n$ 之和小于等于 $2×10^4$ 。

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