"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 , 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.

The first line contains three integers n,m,p (1 \leq n,m \leq 2*10^5, 5\leq p \leq 10^9).

The next m lines describe the roads. Each line contains three integer x_i,y_i,z_i(1\leq x_i , y_i\leq n,1 < z_i < p-1) , denoting that there is a road from city x_i to y_i, which takes z_i days.

One integer, denoting the shortest time.