#P17844. [ONTAK 2021]SCI

[ONTAK 2021]SCI

自行车道

一座城市有 NN 个路口和 MM 条不同的双向道路,整体连通。其中前 KK 条道路已经有自行车道,其余道路可以花费给定代价修建自行车道。

求使全部已有自行车道位于同一个自行车道连通分量内的最小新增费用。可以利用中间路口,但不要求覆盖城市的全部路口。

输入格式

第一行 N,M,KN,M,K。接下来 KK 行,每行 u,vu,v 表示已有自行车道。再接下来 M−KM-K 行,每行 u,v,cu,v,c 表示一条尚无自行车道的道路及其建设费用。

输出格式

输出最小新增费用。

数据范围

1≤N≤5001\le N\le500,1≤K≤M≤10001\le K\le M\le1000,K≤8K\le8,1≤u,v≤N1\le u,v\le N,u≠vu\ne v,1≤c≤100001\le c\le10000。没有重边。

样例

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