4055: Sightseeing Trip

时间限制:1000 ms 内存限制:256 MB
上传者:
提交:36 通过:10

题目描述

给定一张无向图,求图中一个至少包含 $3$ 个点的环,环上的节点不重复,并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。在本题中,你需要输出最小环的方案,若最小环不唯一,输出任意一个均可。若无解,输出 `No solution.` 图的节点数不超过 $100$。

输入格式

第一行两个正整数 $n,m$ 表示点数和边数。 接下来 $m$ 行,每行三个正整数 $x,y,z$,表示节点 $x,y$ 之间有一条长度为 $z$ 的边。

输出格式

输出一个最小环的方案:按环上顺序输出最小环上的点。若最小环不唯一,输出任意一个均可。若无解,输出 `No solution.`

输入样例 复制

4 6
1 2 40
1 3 50
1 4 60
2 3 10
2 4 30
3 4 20

输出样例 复制

2 3 4

分类标签