← 返回题目列表

AtCoder · abc308_h

Ex. 做 Q

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

有一个简单的无向图 N 顶点和 M 边缘。 边缘最初被漆成白色。 顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。 边缘 i 连接顶点 A_i 和顶点 B_i,将其涂成黑色所需的成本为 C_i.

“制作 Q”意味着绘制四个或更多边,以便:

  • 除了一个涂成黑色的边缘外,所有边缘都形成一个简单的循环,并且
  • 不形成循环的涂成黑色的边连接循环上的一个顶点和另一个不在循环上的顶点。

确定是否可以提出 Q。如果可以,请找出提出 Q 所需的最小总成本。

约束

  • 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),如果 i \neq 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

输出

如果可以提出一个问题,请打印出这样做所需的最低总成本;否则,打印 -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 需要花费 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