题目描述
给定一张无向图,求图中一个至少包含3个点的环,环上的节点不重复,并且环上的边的长度和最小。该问题被称为无向图的最小环问题。在本题中,你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。若无解,输出$No$ $solution.$。
输入格式
第一行包含两个正整数$n$和$m$,分别表示图中有$n$个节点$m$条边。接下来$m$行每行三个正整数$x$,$y$,$v$描述一条$x$与$y$之间权值为$v$的无向边。
输出格式
输出仅一行,包含$No$ $solution.$或若干个空格隔开的正整数,以描述所求的最小环。
若有多种方案,仅要求输出任意一种。对于任意一种方案,请按环上的遍历顺序输出编号。
样例
Input
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Output
1 3 5 2
数据规模
对于$100\%$的数据,保证$1<=n<=100$,$1<=m<=10000$,$1<=vi<=500$。
题目来源
$POJ1734$。
特别注意
本题数据已经可以spj,于2019年9月3日


