Description

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 < xi , yi , zi >, means that there is a road from xi to yi , which takes zi 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 zi to f(zi). $$ f(x)=\frac{1+x}{1-x}mod \quad p \qquad x∈(1, p − 1) $$ mod p x ∈ (1, p − 1)

It is guaranteed that p is a prime number and f(zi) 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 = ab mod p, which is equivalent to find an integer b^-1 (1 ≤ b^-1 ≤ p − 1) to meet b^-1 ∗ b = 1 mod p, can be translated into calculating f = a ∗ b^-1.

Input

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.

Output

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