History

题号：NC222873
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

            "The monster from Corsica landed at the port of Juan."
                                                    "The unspeakable Cannibal is approaching Graz."
                                                    "The despicable usurper entered Gellernoble."
                                                            "Napoleon Bonaparte takes Lyon."
                                                    "General Napoleon approaches Fontainebleau."
                                            "The supreme emperor arrived in his faithful Paris today!"

One day when you wake up,you find that you have become Napoleon! Now,you will lead the army to capture Paris and rebuild your own dynasty!

In France, there are $n_{}$ cities and $m_{}$ directed roads. Each road is defined as $<x_i, y_i, z_i>$ , means that there is a road from $x_i$ to $y_i$ , which takes $z_i$ days. It is guaranteed that there is no self loop.

However,the battlefield is changing rapidly,so the time required to move on the road is constantly changing. Specifically,every time after you move on one road,the time spent on all roads changes from $z_i$ to $f(z_i)$ .

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

It is guaranteed that $p_{}$ is a prime number and $f(z_i)$ is defined in any time.

Now,please try to use she shortest time to arrived in the city $n_{}$ from the city $1_{}$ .

It is guaranteed that you can arrived in the city $n_{}$ .

Hint: Calculating $f = \frac{a}{b} \mod p$ , which is equivalent to find an integer $b^{-1}~(1 \le b^{-1} \le p - 1)$ to meet $b^{-1} * b = 1 \mod p$ , can be translated into calculating $f = a * b^{-1} % p$ .

输入描述:

The first line contains three integers    . 

The next  lines describe the roads. Each line contains three integer  , denoting that there is a road from city  to ,which takes  days.

输出描述:

One integer,denoting the shortest time.

示例1

输入

复制

输出

复制