题目描述

$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$ 再会的那一刻。

输入格式

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

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

这 $m$ 行中前 $k$ 行表示 $Lily$

所知道的关键解读。

输出格式

$k + 1$ 行每行有一个整数 $ans$ 。

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

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

输入样例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

输出样例1

21
19
20

数据范围

$1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^9$ 对于 $30\%$ 的数据满足 $1 ≤ n ≤ 100,1 ≤ m ≤ 400,1 ≤ k ≤ 5$

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

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

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