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

Input
Output
6 6 1 2 7 2 3 5 3 6 4 1 4 8 4 5 10 5 6 9
12

Constraints

Time limit: 5.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue