meixiuxiu学图论

是一个不喜欢图论的孩纸,但是比赛碰到图论的题目怎么办呢,所以她准备怒刷图论500道
这一天,她刚学完有关最小生成树的算法,碰到了碰到了一个图论的问题,作为和数学和dp选手,他是百思不得解,于是就向请教。
这个问题是这样的:给定一个有个点条边的有权连通图,图中可能会存在一些环,对于任意一个环,定义,对于所有的环而言,我们要求的是
她一下就看出了解法,于是就更加认为是一个,因此不接受他的问题,并把问题扔给了你,你们会么?

输入第一行有一个,表示样例个数。
每个样例开始一行有两个整数, ,表示图中节点数和边数。
接下来行,每一行有三个整数,,,表示每一条边的起点,终点和权值。

每一个样例输出一行。
如果问题有解则输出解,否则输出"No solution!"。(不包含引号)

2
3 2
1 2 3
2 3 4
5 6
1 2 1
2 3 2
1 3 4
3 4 5
4 5 2
5 3 8

No solution!
4

第一个样例,没有环,所以无解
第二个样例有两个环,分别是,第一个环里的最大值是,第二个是,所以答案是4。