Shortest Path with Discount

You are given a directed weighted graph with N nodes and M edges. The nodes are numbered from 1 to N. Each edge has a positive weight, representing the cost to travel between two nodes.

You have a special discount coupon that you can apply to at most one edge in the entire graph. This coupon reduces the weight of the chosen edge to half its value (using floor division, i.e., newweight = floor(originalweight / 2)).

Your task is to find the minimum possible cost to travel from the starting node 1 to the destination node N. You can choose to use the coupon on any single edge, or not use it at all if the original shortest path is already optimal.

Input Format:

The first line contains two space-separated integers: N (number of nodes) and M (number of edges).

The next M lines each describe an edge with three space-separated integers: u, v, and w. This represents a directed edge from node u to node v with a weight of w.

Output Format:

The output should be a single integer representing the minimum cost to travel from node 1 to node N.

Note:

Nodes are 1-indexed.

All edge weights are positive.

If you apply the discount to an edge of weight w, its new weight becomes w / 2 (integer division).

If node N is unreachable from node 1, the cost is considered infinite. In this problem, it's guaranteed that a path exists.