1419. [POJ 1734]观光旅行

【题目描述】

桑给巴尔岛上的阿德尔顿镇有一家旅行社，它已决定为其客户提供除了许多其他名胜之外的景点。为了尽可能地从景点赚取收入，该机构已经接受了一个精明的决定：有必要找到在同一地点开始和结束的最短路线。你的任务是写一个找到这样的路线的程序。

镇内有 $N$ 个交叉点，编号从 $1$ 到 $N$。同时有 $M$ 条双向路，编号从 $1$ 到 $M$。两个交叉点可以由多条道路连接，但没有道路将交叉点与自己连接。

每条观光环线都是一系列道路编号 $y_1, \dots, y_k，k > 2$。道路 $y_i \ (1 \le i \le k-1)$连接交叉点 $x_i$ 和 $x_ {i + 1}$，道路 $y_k$ 连接交叉点 $x_k$ 和 $x_1$。

所有的数字 $x_1, \dots, x_k$ 应该是不同的。

观光路线的长度是观光路线上所有道路长度的总和，即 $\mathrm{L}(y_1) + \mathrm{L}(y_2) + \dots + \mathrm{L}(y_k)$ 其中 $\mathrm{L}(y_i)$ 是道路 $y_i$ 的长度 $(1 \le i \le k)$。

你的程序必须找到这样一条观光路线，其长度最短，或者说明这是不可能的，因为镇上没有观光环线。

【输入格式】

第一行输入包含两个正整数：交叉点 $N \le 100$ 和道数 $M \le 10000$。

接下来的 $M$ 行中的每一行描述一条道路。 它包含 $3$ 个正整数：第一个交点的编号，第二个交点的编号和道路的长度（小于 $500$ 的正整数）。

【输出格式】

输出中只有一行，一个字符串。如果没有任何观光路线，输出'No solution.'

或者列出最短观光路线上所有交叉点的编号，以便让我们知道如何设计路线（即从我们对观光路线的定义中的数字 $x_1$ 到 $x_k$），由空格分离。

如果有多条最小长度的观光路线，您可以输出其中任何一条。

【样例输入】

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

【提示】

【来源】

《算法竞赛进阶指南》 POJ1734