Byteland 有 $n$ 座城市，编号从 $1$ 到 $n$，由 $n-1$ 条双向道路连接。对于每一对城市，居民都可以通过这些道路从一个城市到达另一个城市（这意味着 Byteland 的道路网络是一棵树）。

该国的女王 Ghaliyah 决定建造 $k$ 个新工厂。为了避免污染，她要求工厂只能建在只有一个连接道路的城市（这意味着该城市是道路网络中的一个叶子节点）。此外，一个城市只能建一个工厂。

作为皇家设计师，你的任务是安排这些工厂的建设，并使任意两个工厂之间的距离之和最小。

输入格式

输入包含多个测试用例。第一行是一个正整数 $T$，表示测试用例的数量，最多为 $10^3$。

对于每个测试用例，第一行包含两个整数 $n$ ($2 \le n \le 10^5$) 和 $k$ ($1 \le k \le 100$)，分别表示 Byteland 的城市数量和需要建造的新工厂数量。

接下来的 $n-1$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n$) 和 $w$ ($1 \le w \le 10^5$)，描述了一条连接城市 $u$ 和城市 $v$ 的道路，其长度为 $w$。

保证道路网络中的叶子节点数量不小于 $k$，且所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是从 $1$ 开始的测试用例编号，$y$ 是任意两个工厂之间距离之和的最小值。

样例

输入 1

2
4 2
1 2 2
1 3 3
1 4 4
4 3
1 2 2
1 3 3
1 4 4

输出 1

Case #1: 5
Case #2: 18