4584: H
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：2
通过：0
题目描述
有一天当你醒来时，你发现自己变成了拿破仑！现在，你将率领军队占领巴黎，重建自己的王朝！
在法国，有n个城市和m条定向道路。每条路定义为< xi、yi、zi >，意思是有一条从xi到yi的道路，需要zi days。保证没有自我循环。
然而，战场瞬息万变，因此在路上移动所需的时间也在不断变化。具体来说，每在一条道路上移动后，在所有道路上花费的时间都会从zi变为f（zi）。
mod p x ∈ （1， p − 1）
保证 p 是素数，并且 f（zi） 在任何时间都定义。
现在，请尽量利用她最短的时间从城市1到达城市n。
保证您可以到达城市n。
提示：计算 f = ab mod p，相当于找到一个整数 b-1 （1 ≤ b-1 ≤ p − 1） 来满足 b-1 ∗ b = 1 mod p，可以转换为计算 f = a ∗ b-1。
输入格式
The first line contains three integers n, m, p (1 ≤ n, m ≤ 2 ∗ 10e5, 5 ≤ p ≤ 10e9). The next m lines describe the roads. Each line contains three integers xi , yi , zi(1 ≤ xi , yi ≤ n, 1 < zi < p − 1) , denoting that there is a road from city xi to yi ,which takes zidays.
输出格式
One integer,denoting the shortest time.
输入样例 复制
4 5 5
1 2 2
3 4 2
1 3 2
2 4 2
2 3 3输出样例 复制
4