#P4663. Hack
Hack
Hack
题目描述
通信网络有 个结点和若干有向边。信息从 号结点发出,沿有向边一直传到 号结点。同一个结点或同一条边可以在一次传递过程中多次经过。
你可以预先入侵若干条边。每次信息经过一条被入侵的边时,都会被截获一次。只有所有可能的传递路线都恰好被截获一次,入侵才成功。
入侵一组边的代价为这组边各自代价的总和。求成功方案的最小代价。
输入格式
第一行两个整数 。
接下来 行,每行三个整数 ,表示一条从 到 的有向边,入侵这条边的代价为 。
输出格式
输出一行一个整数,表示最小代价。若不存在成功方案,输出 。
6 7
0 1 5
0 2 5
1 3 1
2 4 1
4 1 1
3 5 5
4 5 5
6
样例解释
可以入侵 与 两条边,总代价为 。
数据范围
,,,。保证至少存在一条从 到 的路线。