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 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 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