#P3094. [Acm BeiJing2012]Peach Blossom Spring
[Acm BeiJing2012]Peach Blossom Spring
桃花源(Peach Blossom Spring)
题目背景
东晋诗人陶渊明在《桃花源记》中写到一个与世隔绝的村庄。村民的先祖为躲避秦时的战乱来到这里,数百年后才有一名渔夫发现他们。后来,人们在村庄遗迹中找到了一份关于修路和避难的文书。

题目描述
村里有 座房屋和 条损坏的双向道路。房屋编号为 至 。最前面的 座房屋各住着一户人家,最后面的 座房屋各有一处避难所。
村民可以修复一些道路,让每户人家都能沿修好的道路到达一处避难所。避难所可以自由分配,但每处至多容纳一户。不同家庭可以共用道路,同一条道路修复一次,费用只计一次。
求能使所有家庭都到达避难所的最小修路费用。
输入格式
第一行包含整数 (,,,)。
接下来 行,每行三个整数 ,表示房屋 之间有一条道路,修复费用为 (,)。
输出格式
输出一行一个整数。有合法方案时输出最小总费用,否则输出 -1。
样例
4 3 1
4 2 10
3 1 9
2 3 10
29
6 7 2
1 5 1000
2 6 1000
1 3 1
2 3 1
3 4 1
4 5 1
4 6 1
5