P5060 旅行

$jjc$ 非常喜欢旅行~~（smy）~~！

NOIP 2018 已经结束了，jjc 决定去全国各地旅行，每个地方都有许多巨佬，他拥有一张地图来帮助他规划一条从 $A $ 地到 $B$ 地的路线，地图上有 $N$ 个地点编号为 $1\sim N$ ，有 $M$ 条道路将不同（或相同）地点有向连通。 现在，jjc 已经知道了通过第 $i$ 条路从 $u_i$ 地直接走到 $v_i$ 地会遇到多少名巨佬，他将记录遇见的每一名巨佬的名字（不管是否记录过）。但是，每记录一名巨佬的名字就需要使用一张便签，便签以袋为单位出售，jjc 选购的便签每一小袋有 $P$ 张。jjc 不希望他购买的便签被浪费，因此他希望他旅程结束后他购买的每一袋便签都**恰好**被用完。除此以外，jjc 正在存钱来......QwQ，他得减少消费，因此他希望这次旅行能消耗尽量少的便签。 然而，他不知道怎么才能找到最合适的路径，作为巨佬中的一员，你能帮 jjc 解决这个问题，找到符合条件的最佳路径吗？

第一行，给出五个整数，依次是 $N$、$M$、$P$、起点 $A$ 的编号、终点 $B$ 的编号 从第二行到第 $M+1$ 行描述道路的信息，每行三个整数，依次是第 $i$ 条道路连接的两个地点的起点编号 $u_i$、终点编号 $v_i$ 及这条道路上会遇见的巨佬数量 $num_i$

若存在满足条件路线，请输出两行，第一行一个整数，表示选择最佳路径上会遇见的巨佬总数，第二行输出从起点 $A$ 到终点 $B$ 的最佳路径的详细路线，数据保证答案是唯一的。 若无满足条件的路线，请输出一行一个字符串“`jjc fails in travelling`”（不含引号）。

本题有 $3$ 个 $Subtask$。 对 $30\%$ 的数据，$2\le N\le 100$，$2\le M\le 5000$，$1\le P\le 50$； 对另外 $20\%$ 的数据，$2\le N\le 5\times 10^4$，$M\le 2×10^5$，$P=1$； 对另外 $50\%$ 的数据，$2\le N\le 5\times 10^4$，$M\le 2\times 10^5$，$1\le P\le 50$； 对于所有数据，$1\le A,B,u_i,v_i\le N$，$0\le num_i\le 10^8$。 By：学无止境