#abc308h. [abc308_h]Make Q

[abc308_h]Make Q

Problem Statement

There is a simple undirected graph with NN vertices and MM edges. The edges are initially painted white. The vertices are numbered 11 through NN, and the edges are numbered 11 through MM. Edge ii connects vertex AiA_i and vertex BiB_i, and the cost required to paint it black is CiC_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

  • 4leqNleq3004\\leq N \\leq 300
  • 4leqMleqfracN(N1)24\\leq M \\leq \\frac{N(N-1)}{2}
  • 1leqAi<BileqN1 \\leq A_i < B_i \\leq N
  • (Ai,Bi)neq(Aj,Bj)(A_i,B_i) \\neq (A_j,B_j), if ineqji \\neq j.
  • 1leqCileq1051 \\leq C_i \\leq 10^5
  • All input values are integers.

Input

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

NN MM A1A_1 B1B_1 C1C_1 A2A_2 B2B_2 C2C_2 vdots\\vdots AMA_M BMB_M CMC_M

Output

If one can make a Q, print the minimum total cost required to do so; otherwise, print \-1\-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,52,3,4,5, and 66,

  • edges 2,4,52,4,5, and 66 forms a simple cycle, and
  • edge 33 connects vertex 33 (on the cycle) and vertex 11 (not on the cycle),

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


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