农夫约翰（Farmer John）的奶牛们希望在农场的 $N$（$1 \le N \le 200$）个牧场（编号为 $1 \dots N$）之间自由穿梭，尽管这些牧场之间被森林隔开。奶牛们希望在某些牧场对之间维护一些小路，以便它们可以利用这些被维护的小路从任意一个牧场前往任意其他牧场。奶牛们可以沿着被维护的小路双向通行。

奶牛们不自己建造小路。相反，它们维护它们所发现的野生动物小路。在任何一周，它们都可以选择维护它们所知道的任何或全部野生动物小路。

奶牛们总是充满好奇心，它们在每周开始时都会发现一条新的野生动物小路。然后，它们必须决定该周要维护的小路集合，以便它们能够从任意一个牧场前往任意其他牧场。奶牛们只能使用它们当前正在维护的小路。

奶牛们总是希望最小化它们必须维护的小路总长度。奶牛们可以选择维护它们所知道的野生动物小路的任意子集，而不管前一周维护了哪些小路。

野生动物小路（即使在被维护时）也绝不是笔直的。连接相同两个牧场的两条小路可能具有不同的长度。虽然两条小路可能会交叉，但奶牛们非常专注，除了在牧场中，它们拒绝在其他地方换路。

在每周开始时，奶牛们会描述它们发现的野生动物小路。如果存在这样一组小路，你的程序必须输出奶牛们该周为了能够从任意牧场前往任意其他牧场而必须维护的小路的最小总长度。

输入格式

• 输入的第一行包含两个空格分隔的整数 $N$ 和 $W$。$W$ 是程序将要处理的周数（$1 \le W \le 6000$）。
• 对于每周，读取单行，其中包含新发现的野生动物小路。该行包含三个空格分隔的整数：该小路的两个端点（牧场编号）以及该小路的整数长度（$1 \dots 10000$）。没有野生动物小路的两个端点是同一个牧场。

输出格式

在你的程序得知新发现的野生动物小路后，应立即输出单行，其中包含奶牛们为了能够从任意牧场前往任意其他牧场而必须维护的小路的最小总长度。如果没有小路集合能让奶牛们在任意两个牧场之间通行，则输出 -1。

在输出最后一周的答案后，你的程序必须退出。

样例

输入样例 1

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

输出样例 1

-1
-1
-1
14
12
8

说明 1

• 第 1 周：发现小路 $1-2$（长度 $10$）。没有小路连接牧场 $4$ 与其他牧场，输出 -1。
• 第 2 周：发现小路 $1-3$（长度 $8$）。没有小路连接牧场 $4$ 与其他牧场，输出 -1。
• 第 3 周：发现小路 $3-2$（长度 $3$）。没有小路连接牧场 $4$ 与其他牧场，输出 -1。
• 第 4 周：发现小路 $1-4$（长度 $3$）。维护小路 $1-4$（长度 $3$）、$1-3$（长度 $8$）和 $3-2$（长度 $3$），总长度为 $14$。
• 第 5 周：发现小路 $1-3$（长度 $6$）。维护小路 $1-4$（长度 $3$）、$1-3$（长度 $6$）和 $3-2$（长度 $3$），总长度为 $12$。
• 第 6 周：发现小路 $2-1$（长度 $2$）。维护小路 $1-4$（长度 $3$）、$2-1$（长度 $2$）和 $3-2$（长度 $3$），总长度为 $8$。

数据范围

• $1 \le N \le 200$
• $1 \le W \le 6000$
• 小路长度在 $1 \dots 10000$ 之间。

子任务

对于每个测试用例，如果你的程序输出了正确的答案，你将获得该测试用例的满分。每个测试用例不设部分分。