### 问题描述 小蓝的村子道路可以看成一幅联通树形图（数据结构中的“树”），小蓝的家所在的位置是 $1$ 号点，也就是根节点。其他人的家都可以看成一个节点。总共有 $n$ 个节点，$n-1$ 条边，每条边就是一条线路，每条道路会有一个长度 $t_i$ 。 村里获得了一笔经费，这笔经费可以足够整改 $k$ 次道路，每一次整改可以将这条线路的长度减少 $ \lfloor \frac {t_i} {2} \rfloor$。也就是说，对一条长度为 $t$ 的线路进行一次整改，它的时延由 $t_i$ 变为 $\lceil \frac {t_i} {2} \rceil$，并且一条线路可以经历多次整改。 我们设 $f(x)$ 为从 $1$ 号点到 $x$ 点需要的长度（注意，只是单向的，所以你不需要考虑回去的道路），由于小蓝需要长期发布一些消息，所以小蓝想知道 $\sum _{i=2} ^n f(i)$ 最小为多少 形式化的说：给定一颗 $n$ 个节点的带权树形图，你有 $k$ 次机会，每次你可以选择一条边，使得它的边权从 $t_i$ 变为 $\lceil \frac {t_i} {2} \rceil$，询问你所有点到根节点的路径和最小是多少？ ### 输入格式 第一行输入一个整数 $T$ ，代表测试组数。 对于每组输入，由以下部分组成： 1. 第一行两个整数 $n, k$。 2. 接下来 $n - 1$ 行，每行三个整数 $u_i, v_i, t_i$ ，表示 $u_i$ 和 $v_i$ 之间有一条 $t_i$ 时延的线路。 **数据保证是一棵树。** ### 输出格式 输出 $T$ 行，每行一个整数 $W$ ，表示最小时延和。 ### 样例输入 ``` 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 ``` ### 样例输出 ``` 12 46 1989174327 ``` ### 说明 对于个测试组： $ 2 \le n \le 10^4, k \le 10^9, 1 \le u_i, v_i \le n, 1 \le t_i \le 10^9$ 。 $\sum n \le 2 \times 10^6$ 。