Single Discount

Alex lives in city 1 and wants to reach city n. He wants to find the minimum-price flight route, taking into account the availability of a discount coupon. The discount coupon can be used only once to halve the price of a single flight during the route. When he uses the discount coupon for a flight with a price of x, the price becomes .
Find the price of the cheapest route from city 1 to city n.

Input

The first line contains two space-separated integers n and m (), representing the number of cities and the number of flights, respectively.

The next m lines describe the flights. Each line contains three space-separated integers a, b, and (), indicating a bidirectional flight from city a to city b with a price of .

Output

Print a single integer, representing the price of the cheapest route from city 1 to city n.

Examples