Description

Lily 忘不掉小时候临别前与 Nana 一起出逃的夜晚，两人为了探索宇宙的真相而沿着铁路轨道前行，望见从天际线涌出的大鱼浮在夜空里。从那以后 Lily 便未曾停止过钻研宇宙的秘密。

秘密啊，总是会有那么一两个的。以浮起的大鱼为典型，Lily 所在的世界发生了 $n$ 件关于宇宙的重大事件。阴谋诡计，完全犯罪，宇宙的暗物质，事件与事件之间看似互不相干，但 Lily 每天阅读着关于宇宙的书籍，从书籍最后一页总结出 $m$ 段解读，每段解读都能将其中某两件事件联系起来。

大人们希望 Lily 揭露部分已经得到的解读，使所有发生的事件都能被串联起来。但是 Lily 清楚，如果这些解读暴露，班里大概有一半的同学会开始计划着出逃——秘密的揭露都是需要 Lily 付出代价的，假设每一段解读的揭露需要付出的代价可以被量化，第 $i$ 段解读的揭露需要付出的代价为整数值 $w_i$ 。Lily 需要付出的总代价为，在确保解读们能将所有事件联系起来的前提下，Lily 所揭露的所有解读的代价之和。

Lily 知道，其中有 $k$ 段解读是关于世界真理的关键解读，是承载着 $70$ 亿的秘密，这些解读被透露的数量将直接决定着人类延续的可能性。人们议论纷纷，说着或许只有这两个孩子才能拯救世界，$70$ 亿人所凝聚的正义将 $2$ 人的自由剥夺，迫切地想要知道 Lily 给出的答案。

你想要知道，对于 $0$ 到 $k$ 中所有整数 $i$ ，Lily 透露了一部分解读，能将所有事件联系起来，且其中正好 有 $i$ 个关键解读的前提下，Lily 需要付出的最小总代价。

“我不明白啊”，Lily 这样的哭了。她会坚守着秘密，按照约定等待着与 Nana 再会的那一刻。

Input Format

第一行有三个整数 $n, m, k$ ，分别表示事件数量，解读总数和关键解读的数量。

紧接着 $m$ 行每行有三个整数 $u, v, w$ ，分别表示一种能将事件 $u$ 与事件 $v$ 联系起来的解读，但是这解读的揭露需要付出 $w$ 的代价。

这 $m$ 行中前 $k$ 行表示 Lily 所知道的关键解读。

Output Format

$k + 1$ 行每行有一个整数 $ans$ 。其中第 $i$ 行整数 $ans_i$ 表示揭露正好 $i − 1$ 个关键解读的。

数据保证在所有关键解读都不揭露的情况下，剩余的解读能将所有事件联系在一起。

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

21
19
20

Hint

数据范围

$1 \le u, v \le n, 1 \le w \le 10^9$；

对于 $30\%$ 的数据满足 $1 \le n \le 100, 1 \le m \le 400, 1 \le k \le 5$；

对于另外 $30\%$ 的数据满足 $1 \le n \le 10000, 1 \le m \le 1000000, 1 \le k \le 20$；

对于剩下 $40\%$ 的数据满足 $1 \le n \le 10000, 1 \le m \le 1000000, 1 \le k \le 50$。

赛题被启用的时候，小小的行星上已经有 $80$ 亿人了。