#2931. [GDKOI]Himitsu

[GDKOI]Himitsu

题目描述

img

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

秘密啊,总是会有那么一两个的。

以浮起的大鱼为典型,LilyLily 所在的世界发生了 nn 件关于宇宙的重大事 件。

阴谋诡计,完全犯罪,宇宙的暗物质,事件与事件之间看似互不相干,但 LilyLily 每天阅读着关于宇宙的书 籍,从书籍最后一页总结出 mm 段解读,每段解读都能将其中某两件事件联系起来。

img

大人们希望 LilyLily 揭露部分已经得到的解读,使所有发生的事件都能被串联起来。

但是 LilyLily 清楚,如果这 些解读暴露,班里大概有一半的同学会开始计划着出逃——秘密的揭露都是需要 LilyLily 付出代价的,假设每一 段解读的揭露需要付出的代价可以被量化,第 ii 段解读的揭露需要付出的代价为整数值 w i 。LilyLily 需要付出 的总代价为,在确保解读们能将所有事件联系起来的前提下,LilyLily 所揭露的所有解读的代价之和。

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

你想要知道,对于 00kk 中所有整数 iiLilyLily 透露了一部分解读,能将所有事件联系起来,且其中正好 有 ii 个关键解读的前提下,LilyLily 需要付出的最小总代价。

img

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

输入格式

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

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

mm 行中前 kk 行表示 LilyLily

所知道的关键解读。

输出格式

k+1k + 1 行每行有一个整数 ansans

其中第 ii 行整数 ansians_i 表示揭露正好 i1i − 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

数据范围

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

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

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

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