You are given a directed graph with $$$n$$$ nodes and $$$m$$$ edges. Your task is to find the minimum-cost path from the source node (node $$$1$$$) to the destination node (node $$$n$$$).
You are allowed to use a discount coupon on at most one edge during your route. This coupon allows you to halve the cost of any one edge, rounding the result down to the nearest integer. That is, if the original cost of an edge is $$$x$$$, the discounted cost becomes $$$\left\lfloor \frac{x}{2} \right\rfloor$$$.
The first line contains two integers $$$n$$$ and $$$m$$$: the number of nodes and the number of edges ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$).
Each of the next $$$m$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$c$$$: there is a directed edge from node $$$a$$$ to node $$$b$$$ with cost $$$c$$$ ($$$1 \le a, b \le n$$$, $$$1 \le c \le 10^9$$$).
It is guaranteed that there is at least one path from node $$$1$$$ to node $$$n$$$.
Print one integer: the minimum possible total cost to travel from node $$$1$$$ to node $$$n$$$, using the discount coupon on at most one edge.
Input:
3 4 1 2 3 2 3 1 1 3 7 2 1 5
Output:
2
Input:
4 4 1 2 3 2 4 3 1 3 10 3 4 10
Output:
4