1398_Hamilton路径

给出一个连通的有向图，求图中顶点1到顶点n的、经过其余顶点一次且仅一次的最短路径及其长度。

单测试用例。

第一行是两个整数N，E，N表示顶点个数( 1 ≤ N ≤ 40 )，E表示弧的数量( N < E < 200 )。

接下来E行，每行是空格分隔的3个整数u, v, l，分别表示从顶点u发出一条长度为l的弧到顶点v。1 ≤ u, v, ≤ N  。 0 < l ≤ 100

注意：可能存在重边。

每个测试用例输出：如果不存该路径，输出一行 "No solution"；

否则，输出两行：第1行，该最短路的长度；第2行，从顶点1到顶点n的最短路，顶点之间用一个空格分隔，要求按路径的顶点次序，前一个顶点必须有弧指向后一个顶点。

5 12
1 2 23
1 3 35
1 4 5
2 3 58
2 4 8
2 5 76
3 2 33
3 4 2
3 5 75
4 2 95
4 3 34
4 5 85

140
1 2 4 3 5