Best Flight Itinerary Under Budget with Minimal Transfers

Problem: Best Flight Itinerary from A to B Under Budget (Min Transfers) Given a directed flight graph and parameters, find an itinerary from source A to destination B. Each flight is a directed edge u -> v with a non-negative cost. You are also given a budget budget. Among all itineraries with total cost <= budget, choose the one with the minimum number of transfers. Transfers are defined as: number of flight legs minus 1 (e.g., A->C->B has 1 transfer). If multiple itineraries have the same minimum transfers, choose the one with the minimum total cost. Input (stdin) First line: n m (number of cities, number of flights) Next m lines: u v cost Last line: A B budget Cities are labeled 0..n-1. Output (stdout) If a feasible itinerary exists, output two integers: min_transfers min_cost If no path from A to B has total cost <= budget, output: -1 -1 Constraints 1 <= n <= 1e5 0 <= m <= 2e5 0 <= cost <= 1e6 0 <= budget <= 1e12 Example Input 4 5 0 1 100 1 3 100 0 2 50 2 3 300 0 3 500 0 3 250 Output 1 200