很久以前，在神秘的大陆上，有一个青蛙王国，由最年长的青蛙——长者统治。这个王国由 $N$ 个城市组成，从东到西依次编号。第 $1$ 个城市位于其他城市的东边，是王国的首都。除首都外，每个城市都向西连接着零个或多个城市，且向东恰好连接着一个城市。

每天在某些城市都会发生一些重大新闻，长者希望尽快得知这些消息。因此，这就是记者蛙的工作，它们跑得比其他任何青蛙都快。一旦某个城市发生了重大新闻，该城市的记者就会带着消息跑向首都。当它到达另一个城市时，它既可以继续跑，也可以在该城市停下来，让另一名记者接力传送。记者蛙们还太年轻、太简单，无法高效地长途奔跑。因此，它们跑过长度为 $L$ 的路径需要消耗 $L^2$ 的时间。此外，每次交接消息都需要消耗 $P$ 的时间来仔细核对消息，因为消息中的任何错误都会让长者非常生气。

现在，你兴奋地接到了这个任务：计算从这些城市之一将消息传送到首都所需的最大时间。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

对于每个测试用例：

第一行包含两个整数 $N$（$N \leq 100\,000$）和 $P$（$P \leq 10\,000$）。

接下来的 $N - 1$ 行中，第 $i$ 行描述第 $i$ 条道路：一行包含三个整数 $u$、$v$ 和 $w$，表示第 $u$ 个城市与第 $v$ 个城市之间有一条长度为 $w$（$w \leq 100$）的边。

输出格式

对于每个测试用例，输出最大时间。

样例

输入 1

3
6 10
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 30
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3
6 50
1 2 4
2 3 5
1 4 3
4 5 3
5 6 3

输出 1

51
75
81

说明

在第二个测试用例中，最佳的传输时间为：

• 第 $2$ 个城市：$16 = 4^2$
• 第 $3$ 个城市：$72 = 4^2 + 30 + 5^2$
• 第 $4$ 个城市：$9 = 3^2$
• 第 $5$ 个城市：$36 = (3 + 3)^2$
• 第 $6$ 个城市：$75 = (3 + 3)^2 + 30 + 3^2$

因此，第 $6$ 个城市的新闻传送到首都所需的时间最长。