1380_经过指定顶点的最短路径

给出一个有n个顶点的有向网，指定其中k个顶点（不含顶点1和顶点n）。求从顶点1到顶点n的，经过那k个顶点的最短路。

单测试用例。

输入的第一行是 顶点数n 和 弧数目e 。 1 ≤ n ≤ 40 ，1 ≤ e ≤ n×n

接下来是 e 行，每行三个整数 i , j , v  ( 其中 0 < i, j ≤ n ， 0 < v ≤ 100 ) ，表示从 顶点i 到 顶点j 的一条权值为v的弧。

接下来是一个正整数k ( 1 ≤ k ≤ n-2 )，接下来是k个正整数，表示必须经过的k个顶点。

每个测试用例：如果不存在满足条件的路径，输出一行 "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
2
2 3

140
1 2 4 3 5