{"raw_statement":[{"iden":"problem statement","content":"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$.\n\"Making a Q\" means painting four or more edges so that:\n\n*   all but one of the edges painted black form a simple cycle, and\n*   the edge painted black not forming the cycle connects a vertex on the cycle and another not on the cycle.\n\nDetermine if one can make a Q. If one can, find the minimum total cost required to make a Q."},{"iden":"constraints","content":"*   $4\\leq N \\leq 300$\n*   $4\\leq M \\leq \\frac{N(N-1)}{2}$\n*   $1 \\leq A_i < B_i \\leq N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$, if $i \\neq j$.\n*   $1 \\leq C_i \\leq 10^5$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$"},{"iden":"sample input 1","content":"5 6\n1 2 6\n2 3 4\n1 3 5\n2 4 3\n4 5 2\n3 5 1"},{"iden":"sample output 1","content":"15\n\nBy painting edges $2,3,4,5$, and $6$,\n\n*   edges $2,4,5$, and $6$ forms a simple cycle, and\n*   edge $3$ connects vertex $3$ (on the cycle) and vertex $1$ (not on the cycle),\n\nso 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$."},{"iden":"sample input 2","content":"4 4\n1 2 1\n2 3 1\n3 4 1\n1 4 1"},{"iden":"sample output 2","content":"\\-1"},{"iden":"sample input 3","content":"6 15\n2 6 48772\n2 4 36426\n1 6 94325\n3 6 3497\n2 3 60522\n4 5 63982\n4 6 4784\n1 2 14575\n5 6 68417\n1 5 7775\n3 4 33447\n3 5 90629\n1 4 47202\n1 3 90081\n2 5 79445"},{"iden":"sample output 3","content":"78154"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}