P11260 [GDKOI2023 普及组] Himitsu

省略了一些不必要的图片。

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 \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$ 亿人了。