#P4158. [POI2007]Railway
[POI2007]Railway
[POI 2007] Railway
题目描述
比特国要缩减铁路网络。铁路网原本连通,每条铁路双向通行,有一个正整数维护费用。现在指定若干座必须保留的车站,要求只保留一部分铁路,使任意两座指定车站仍能相互到达。保留的铁路可以经过其他车站。
设使所有指定车站连通所需的最小总维护费用为 。输出一组总费用不超过 的铁路。保留的铁路应位于同一个连通部分,并与所有指定车站相连。
输入格式
第一行两个整数 (,),表示车站数和铁路数。车站从 到 编号,任意两座不同车站间至多有一条铁路。
保证 。接下来 行,每行三个整数 (,,),表示一条维护费用为 的双向铁路。
最后一行先给出整数 (,),随后按升序给出 座必须保留的车站的编号。
输出格式
第一行两个整数 ,分别为所选铁路的总维护费用和条数。接下来 行,每行两个整数,表示一条所选铁路的两个端点。可以输出任意符合要求的方案。
样例 #1
样例输入 #1
8 11
1 2 6
3 1 5
2 3 8
3 4 9
3 5 10
5 4 3
5 6 9
6 4 8
6 8 8
6 7 7
8 7 10
4 2 5 7 8
样例输出 #1
42 5
2 3
3 5
5 6
6 7
6 8
样例说明
图中实心圆是必须保留的车站,粗线为样例选出的铁路。
