CSES 1195 Flight Discount - Problem Statement

You have a directed graph with N cities and M flights. Each flight has a cost. You get exactly one $50$% discount coupon to use on any single flight.

Find the minimum cost to travel between city $1$ and city N.

Constraints: $N \leq 10^5$, M ≤ $2 \times 10^5$. You must decide where to use the coupon optimally. The challenge is that you cannot just pick the most expensive edge. The best discount depends on which path you take, so you need to consider all options simultaneously.