### 问题描述 蓝桥村的道路图可以看成一幅联通树形图（数据结构中的"树"），其中村政府所在的位置是 $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$，询问你所有点到根节点的路径和最小是多少？ ### 输入格式 第一行一个数字 $T$ ，代表测试组数。 对于每组输入，由以下部分组成： 第一行两个整数 $n, k$，保证 $2 \le n \le 10^4,0 \le k \le 10^9$。 接下来 $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]$ 数据保证是一棵树。并且 $\sum{n} \le 10^5$。 ### 输出格式 输出 $T$ 行，每行一个整数 $W$ ，表示路径和。 ### 样例输入 ```bash 1 3 2 1 2 4 1 3 5 ``` ### 样例输出 ```bash 5 ``` ### 说明 $(1, 2)$ 之间整修一次，$(1,3)$ 之间整修一次。