J. 线路改建
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

湘大的网络拓扑可以看成一幅联通树形图（数据结构中的"树"），其中网络中心所在的位置是 $$$1$$$ 号点，也就是根节点。路由器以及服务器都可以看成一个节点。总共有 $$$n$$$ 个节点，$$$n- 1$$$ 条边，每条边就是一条线路，每条线路会有一个传输时延 $$$t$$$，从节点 $$$a$$$ 到 $$$b$$$ 的时间等于$$$a,b$$$ 之间 最短路径上的传输时延之和。

现在网络中心获得了一笔经费，这笔经费可以足够整改 $$$k$$$ 次线路，每一次整改可以将这条线路的时延减少 $$$\lfloor \frac{t}{2} \rfloor$$$。也就是说，对一条时延为 $$$t$$$ 的线路进行一次整改，它的时延由 $$$t$$$ 变为 $$$\lceil \frac{t}{2} \rceil$$$ ，并且一条线路可以经历多次整改。注意区分"线路"与"路径"的区别，线路只指一条边。

我们设 $$$f(x)$$$ 为从 $$$1$$$ 号点传输消息到 $$$x$$$ 点需要的时延（注意，只是单向的，所以你不需要考虑消息回送），由于网络中心需要长期发布一些消息，所以网络中心想知道经历整改后可以使得 $$$\sum _{i=2}^n{f(i)}$$$ 最小为多少?

$$$\lfloor x \rfloor$$$ 表示不大于 $$$x$$$ 的最大整数，即向下取整。$$$\lceil x \rceil$$$ 表示不小于 $$$x$$$ 的最小整数，即向上取整。

形式化的说：给定一棵 $$$n$$$ 个节点的带权树形图，你有 $$$k$$$ 次机会，每次你可以选择一条边，使得它的边权从 $$$t_i$$$ 变为 $$$\lceil \frac{t_i}{2} \rceil$$$，询问你所有点到根节点的路径和最小是多少？

Input

第一行一个数字 $$$T$$$ ，代表测试组数。

对于每组输入，由以下部分组成：

  1. 第一行两个整数 $$$n, k$$$，保证 $$$2 \le n \le 10^4,~k \le 10^9$$$
  2. 接下来 $$$n - 1$$$ 行，每行三个整数 $$$u_i, v_i, t_i$$$ ，表示 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条 $$$t_i$$$ 时延的线路。$$$u_i,v_i \in [1,n],t_i \in [1,10^9]$$$
  3. 数据保证是一棵树。并且 $$$\sum{n} \le 2 \times 10^6$$$
Output

输出 $$$T$$$ 行，每行一个整数 $$$W$$$ ，表示最小时延和。

Example
Input
3
5 3
2 1 4
3 1 6
4 2 3
5 3 1
5 3
2 1 9
3 2 6
4 3 9
5 4 7
5 3
2 1 586754654
3 1 313989971
4 3 557336509
5 4 748196409
Output
12
46
1989174327