旅行

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

**$NOIP$ $2018$** 已经结束了，$jjc$ 决定去全国各地旅行，每个地方都有许多巨佬，他拥有一张地图来帮助他规划一条从 $A $ 地 到 $B $ 地 的路线，地图上有 $N $ 个地点编号为 $1$~$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$” $($不含引号$)$

2 2 3 1 2
1 2 1
2 2 1

3
1->2->2->2

4 6 3 2 3
2 1 7
2 4 0
4 3 6
1 4 0 
2 3 1
2 3 9

6
2->4->3

3 3 5 1 3
1 2 15
2 3 7
1 3 3 

jjc fails in travelling

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