

Time Limit: 4 sec / Memory Limit: 256 MB
配点 : 点
問題文
モグラは から の番号がついた 個の頂点と 本の辺からなる単純連結無向グラフで表されるような廃坑に住むことにしました。 番目の辺は頂点 と をつないでおり、取り除くために 円かかります。
モグラはいくつかの辺を取り除いて、頂点 から頂点 へ同じ頂点を 回以上訪れないように移動する経路がただ 通りのみ存在するようにしたいです。これを達成するために必要な資金の最小値を求めなさい。
制約
- 与えられるグラフに多重辺や自己ループは存在しない
- 与えられるグラフは連結
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1Copy
4 6 1 2 100 3 1 100 2 4 100 4 3 100 1 4 100 3 2 100
出力例 1Copy
200
以下の図において、赤い破線で表されている辺は取り除かれた辺です。以下の図のように つの辺を取り除くことで 円で達成することが可能です。

入力例 2Copy
2 1 1 2 1
出力例 2Copy
0
はじめから、頂点 から頂点 へのパスが 通りしかないこともあります。
入力例 3Copy
15 22 8 13 33418 14 15 55849 7 10 15207 4 6 64328 6 9 86902 15 7 46978 8 14 53526 1 2 8720 14 12 37748 8 3 61543 6 5 32425 4 11 20932 3 12 55123 8 2 45333 9 12 77796 3 9 71922 12 15 70793 2 4 25485 11 6 1436 2 7 81563 7 11 97843 3 1 40491
出力例 3Copy
133677
Score : points
Problem Statement
Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of vertices numbered through and edges. The -th edge connects Vertices and , and it costs yen (the currency of Japan) to remove it.
Mole would like to remove some of the edges so that there is exactly one path from Vertex to Vertex that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.
Constraints
- There are neither multiple edges nor self-loops in the given graph.
- The given graph is connected.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1Copy
4 6 1 2 100 3 1 100 2 4 100 4 3 100 1 4 100 3 2 100
Sample Output 1Copy
200
By removing the two edges represented by the red dotted lines in the figure below, the objective can be achieved for a cost of yen.

Sample Input 2Copy
2 1 1 2 1
Sample Output 2Copy
0
It is possible that there is already only one path from Vertex to Vertex in the beginning.
Sample Input 3Copy
15 22 8 13 33418 14 15 55849 7 10 15207 4 6 64328 6 9 86902 15 7 46978 8 14 53526 1 2 8720 14 12 37748 8 3 61543 6 5 32425 4 11 20932 3 12 55123 8 2 45333 9 12 77796 3 9 71922 12 15 70793 2 4 25485 11 6 1436 2 7 81563 7 11 97843 3 1 40491
Sample Output 3Copy
133677