3348: 「一本通 3.2 例 1」Sightseeing Trip

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

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

输入

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

输出

输出一个最小环的方案:按环上顺序输出最小环上的点。若最小环不唯一,输出任意一个均可。若无解,输出 `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

样例输出 复制

1 3 5 2

来源/分类