30014 - 经过指定点的最短路径

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

第一行是两个整数 n 和 e，分别表示顶点数和弧数目（1 \le n \le 40，1 \le e \le n \times n）。

接下来 e 行，每行三个整数 i, j, v（0 < i, j \le n，0 < v \le 100），表示从顶点 i 到顶点 j 的一条权值为 v 的弧。

接下来一行是一个正整数 k（1 \le k \le n - 2）。

接下来一行是 k 个正整数，表示必须经过的 k 个顶点。

如果不存在满足条件的路径，输出一行 "No solution"。

否则，输出两行：

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

样例解释 1

第二组询问的最优方案为：选择 3 个物品 1 和 12499999998 个物品 2。

子任务

对于所有测试数据，1 \le n \le 50，1 \le v_i \le 10^5，1 \le c_i \le 10^6，1 \le q \le 10^5，10^{11} \le V \le 10^{12}。