P5060 旅行

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

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

无

无

本题有 $ 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 : $ 学无止境