Problem

A global logistics company routes high-value medical shipments across a network of airports. Each flight leg has a cost (fuel, handling, and priority fees). To meet regulatory and cold-chain requirements, shipments must arrive within a limited number of flight legs. Additionally, the company has a small number of discount coupons that can be applied to at most one leg each, cutting that leg’s cost in half (rounded down).

You are given a directed weighted graph of n airports labeled 0..n-1 and a list of flight legs edges, where each edge is (u, v, w) meaning a flight from u to v costs w.

Task

Return the minimum total cost to travel from src to dst using at most max_legs edges, where you may apply at most k coupons across the path. Applying a coupon to an edge with cost w changes its cost to w // 2.

If it is impossible to reach dst within max_legs legs, return -1.

Input / Output

• Input: n: int, edges: list[list[int]], src: int, dst: int, max_legs: int, k: int
• Output: int minimum achievable cost, or -1

Examples

Example 1

• Input: n=5, edges=[[0,1,10],[1,2,10],[0,2,100],[2,3,10],[3,4,10]], src=0, dst=4, max_legs=4, k=1
• Output: 35
• Explanation: Take 0->1->2->3->4 (4 legs). Costs are 10+10+10+10=40. Apply one coupon to any 10 edge: 10//2=5, total 35.

Example 2

• Input: n=3, edges=[[0,1,5],[1,2,5]], src=0, dst=2, max_legs=1, k=10
• Output: -1
• Explanation: Reaching 2 requires 2 legs, but only 1 is allowed.

Constraints

• 2 <= n <= 2 * 10^4
• 0 <= src, dst < n, src != dst
• 1 <= len(edges) <= 2 * 10^5
• 1 <= w <= 10^9
• 0 <= max_legs <= 2 * 10^4
• 0 <= k <= 30

Notes

• Coupons are optional; you may use fewer than k.
• Multiple edges between the same pair of nodes may exist; treat them as distinct options.
• The hop constraint is at most max_legs, not exactly.