103087: [Atcoder]ABC308 Ex - Make Q

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

问题描述

有一个简单的无向图，包含 N 个顶点和 M 条边。边最初被涂成白色。 顶点从1到N编号，边从1到M编号。 第 i 条边连接顶点 A_i 和顶点 B_i ，涂成黑色所需的费用为 C_i 。

"做一个Q"意味着涂色四条或更多的边，使：

• 除了其中一条边外，其他涂成黑色的边形成一个简单循环，
• 不形成循环的那条边连接了一个在循环上的顶点和另一个不在循环上的顶点。

确定是否可以做一个Q。如果可以，找出使一个Q所需的最小总费用。

约束

• 4≤N≤300
• 4≤M≤N(N-1)/2
• 1≤A_i
• 如果 i≠j，则(A_i,B_i)≠(A_j,B_j)。
• 1≤C_i≤10^5
• 所有输入值都是整数。

输入

输入通过标准输入以以下格式给出：

N M
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

输出

如果可以做一个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 形成一个简单循环，
• 边 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