Ex - Make Q Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

N 頂点 M 辺の単純無向グラフがあり、最初全ての辺は白く塗られています。 頂点には 1 から N までの番号が、辺には 1 から M までの番号がそれぞれ付けられています。 辺 i は頂点 A_i と頂点 B_i を結んでおり、この辺を黒く塗るのにかかるコストは C_i です。

4 本以上の辺を黒く塗ることで以下の条件を全て満たすようにすることを「Q を作る」といいます。

  • 黒く塗られた辺のうちある 1 本以外は、1 つの単純サイクルをなす。
  • 黒く塗られた辺のうち上記のサイクルに含まれない 1 本は、そのサイクルに含まれる頂点と含まれない頂点を結ぶ。

Q を作ることが可能かどうか判定し、可能ならば Q を作るのに必要な最小の総コストを求めてください。

制約

  • 4\leq N \leq 300
  • 4\leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • i \neq j ならば (A_i,B_i) \neq (A_j,B_j)
  • 1 \leq C_i \leq 10^5
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

Q を作ることが可能ならば Q を作るのに必要な最小の総コストを、不可能ならば -1 を出力せよ。

入力例 1

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

出力例 1

15

辺 2,3,4,5,6 を黒く塗ると、

  • 辺 2,4,5,6 が 1 つの単純サイクルをなす
  • 辺 3 が頂点 3（上記のサイクルに含まれる）と頂点 1（上記のサイクルに含まれない）を結ぶ

ため、総コスト 4+5+3+2+1=15 で Q を作ることができます。 他の方法で Q を作っても総コストは 15 以上かかるため、答えは 15 です。

入力例 2

4 4
1 2 1
2 3 1
3 4 1
1 4 1

出力例 2

-1

入力例 3

6 15
2 6 48772
2 4 36426
1 6 94325
3 6 3497
2 3 60522
4 5 63982
4 6 4784
1 2 14575
5 6 68417
1 5 7775
3 4 33447
3 5 90629
1 4 47202
1 3 90081
2 5 79445

出力例 3

78154

Score : 625 points

Problem Statement

There is a simple undirected graph with N vertices and M edges. The edges are initially painted white. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertex A_i and vertex B_i, and the cost required to paint it black is C_i.

"Making a Q" means painting four or more edges so that:

  • all but one of the edges painted black form a simple cycle, and
  • the edge painted black not forming the cycle connects a vertex on the cycle and another not on the cycle.

Determine if one can make a Q. If one can, find the minimum total cost required to make a Q.

Constraints

  • 4\leq N \leq 300
  • 4\leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i) \neq (A_j,B_j), if i \neq j.
  • 1 \leq C_i \leq 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

If one can make a Q, print the minimum total cost required to do so; otherwise, print -1.

Sample Input 1

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

Sample Output 1

15

By painting edges 2,3,4,5, and 6,

  • edges 2,4,5, and 6 forms a simple cycle, and
  • edge 3 connects vertex 3 (on the cycle) and vertex 1 (not on the cycle),

so one can make a Q with a total cost of 4+5+3+2+1=15. Making a Q in another way costs 15 or greater, so the answer is 15.

Sample Input 2

4 4
1 2 1
2 3 1
3 4 1
1 4 1

Sample Output 2

-1

Sample Input 3

6 15
2 6 48772
2 4 36426
1 6 94325
3 6 3497
2 3 60522
4 5 63982
4 6 4784
1 2 14575
5 6 68417
1 5 7775
3 4 33447
3 5 90629
1 4 47202
1 3 90081
2 5 79445

Sample Output 3

78154