7573: [CSES Problem Set] Flight Discount
[Creator : ]
Description
Your task is to find a minimum-price flight route from Syrjälä to Metsälä.
You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.
You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.
Input
The first input line has two integers $n$ and $m$: the number of cities and flight connections. The cities are numbered $1,2,\ldots,n$. City $1$ is Syrjälä, and city $n$ is Metsälä.
After this there are $m$ lines describing the flights. Each line has three integers $a, b, c$: a flight begins at city $a$, ends at city $b$, and its price is $c$. Each flight is unidirectional.
You can assume that it is always possible to get from Syrjälä to Metsälä.
After this there are $m$ lines describing the flights. Each line has three integers $a, b, c$: a flight begins at city $a$, ends at city $b$, and its price is $c$. Each flight is unidirectional.
You can assume that it is always possible to get from Syrjälä to Metsälä.
Output
Print one integer: the price of the cheapest route from Syrjälä to Metsälä.
When you use the discount coupon for a flight whose price is $x$, its price becomes $\lfloor x/2 \rfloor$ (it is rounded down to an integer).
When you use the discount coupon for a flight whose price is $x$, its price becomes $\lfloor x/2 \rfloor$ (it is rounded down to an integer).
Constraints
$2≤n≤10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$
Sample 1 Input
3 4
1 2 3
2 3 1
1 3 7
2 1 5
Sample 1 Output
2