Babu rao , recently came to know about a scheme where a pizza would be delivered free of cost if it doesn't reaches on time, so he cleverly orders the pizza to a location where the delivery man can not reach on the desired time. But recently our mighty Raju has joined the pizza delivery service and he has to delivery pizza to Babu rao .In order to deliver pizza Raju has to use Trains where a train move from X station to Y in T minutes. Raju knows that the location to deliver pizza is not reachable within time ,but he has a LIMITED SCHEME where he can teleport and this will reduce the time taken by any one of the train by (integer division) 1/k. 

Formally there are N stations and M trains each station is numbered 1,2,3..N ,Raju is  currently at station 1 and babu rao is at Nth station and raju has to reach to babu rao in shortest possible time where he can use LIMITED SCHEME to reduce the time taken by any train to reach from it station X to Y by (integer division) 1/k [ONLY ONCE] .

Find the minimum possible time in which raju can deliver pizza to babu rao.

INPUT :

1) First line contains 3 spaced integers denoting number of stations (N) , number of trains(M) and K.

2) Next M lines contains 3 spaced integers where ith line denotes starting station(u) , ending station(v) and time taken by ith train.

CONSTRAINTS:

1 <= N <= 10^5

1<= M<= 2*10^5;

x,y=>[1,N]

1 <= T,K <= 10^9

OUTPUT:

Find minimum possible time in which raju can deliver pizza to babu rao.