题目描述

孙德尔本斯的老虎希望在 $N$ 块田地（编号 $1$ 到 $N$）之间自由穿行，尽管它们之间被树木隔开。老虎希望维护一些田地之间的小路，这样它们就可以通过维护的小路从任意一块田地到达任意另一块田地。老虎可以沿着维护的小路双向行走。

老虎并不自己修建小路，而是维护它们发现的鹿道。每周，它们可以选择维护已经知道的部分或全部鹿道。出于好奇，每周开始时老虎会发现一条新的鹿道。它们必须决定当周要维护哪些小路，以便可以从任意田地到达任意另一块田地。老虎只能使用当前正在维护的小路。

老虎总是希望维护的总长度最小。老虎可以选择维护已知的任何鹿道子集，无论前一周维护了哪些小路。鹿道（即使被维护）从不笔直。连接同一对田地的两条小路可能长度不同。虽然两条小路可能交叉，但老虎非常专注，它们只会在田地处切换小路。每周开始时，老虎会描述它们发现的新鹿道。你的程序必须输出当周老虎为了能自由往返于任意田地之间所需维护的最小总长度，如果存在这样一组小路的话；否则输出 -1。

输入格式

输入第一行包含一个整数 $T$（$\leq 25$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $N$（$1 \leq N \leq 200$）和 $W$（$1 \leq W \leq 6000$），$W$ 是程序需要覆盖的周数。

接下来 $W$ 行，每行包含三个整数，描述老虎当周发现的新鹿道。前两个数字表示端点的田地编号，第三个数字表示鹿道的长度（$1$ 到 $10000$）。没有一条鹿道的两端是同一个田地。

输出格式

对于每个测试用例，首先输出一行 Case i:，其中 $i$ 是从 1 开始的测试用例编号。

然后对于每一周，输出一行，包含当周老虎为了能自由往返于任意田地之间所需维护的最小总长度。如果不存在这样的小路集合，输出 -1。

样例

1
4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2

Case 1:
-1
-1
-1
14
12
8

样例解释

无

数据范围

见题面。