{"problem":{"name":"Ex - Make Q","description":{"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 $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc308_h"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc308_h","tags":[],"sample_group":[["5 6\n1 2 6\n2 3 4\n1 3 5\n2 4 3\n4 5 2\n3 5 1","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$."],["4 4\n1 2 1\n2 3 1\n3 4 1\n1 4 1","\\-1"],["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","78154"]],"created_at":"2026-03-03 11:01:14"}}