4510 - 第十课:最小环

给定一个包含n个顶点的无向图,以及m条边。
求出该图中最小简单环(边权之和最小)。
注:简单环是顶点不重复的环,至少包含3个顶点。
 

输入

第一行输入两个整数$ n(1 \le n \le 100), m(0 \le m \le 10^4) $。
接下来m行,每行输入三个整数$ a_i, b_i(1 \le a_i, b_i \le n), w_i(1 \le w_i \le 500) $,表示$ a_i $和$ b_i $之间有一条边权为$ w_i $的无向边。
 

输出

若不存在环,则输出"No solution.",否则输出最小环的边权值之和。

样例

输入

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出

61
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题