# 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