题目背景

“来自科西嘉的怪物在儒安港登陆。。”

“不可明说的吃人魔王向格腊斯逼近。。”

“卑鄙无耻的窃国大盗进入格尔勒诺布尔。”

“拿破仑·波拿巴占领里昂”

“拿破仑将军接近枫丹白露。”

“至高无上的皇帝陛下于今日抵达自己忠实的巴黎！”

当你醒来的时候，你发现你已经变成了拿破仑！现在，你将带领军队攻占巴黎，重建自己的王朝！

题目描述

在法国，有$n$个城市和$m$条向道路。每条道路被定义为$<x_i,y_i,z_i>$，表示从$x_i$到$y_i$有一条路用时$z_i$天的道路。保证没有自环。

然而，战场瞬息万变，因此在路上行进所需的时间也在不断变化。具体来说，每次在一条道路上行驶后，所有道路所需要花费的时间都会从$z_i$变为$f(z_i)$

$$f(x)=\frac{1+x}{1-x} \ \ \ mod\ \ p \ \ \ x\in (1,p-1) $$

题目保证$p$是质数，因此$f(z_i)$在任何时候都是定义的。

现在，请计算从$1$号城市到达$n$号城市所需要的最短时间，题目保证你可以到达$n$市。

输入格式

第一行读入三个正整数$n,m,p$。

对于接下来$m$行，每行读入三个数字$x_i,y_i,z_i$三个数字，描述一条道路。

输出格式

输出一个数字，表示所需要的最短时间。

4 5 5
1 2 2
3 4 2
1 3 2
2 4 2
2 3 3

4

提示

对于$30\%$的数据，$1\le n,m \le 5 \cdot 10^3$。

对于$100\%$的数据，$1 \le n,m \le 2 \cdot 10^5, 5\le p \le 10^9,1\le x_i,y_i \le n,1< z_i < p-1$。