You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

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

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

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

题目描述

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

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

题目保证$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$。