Cheapest Flight Itinerary

A traveler wants to fly from origin A to destination B with at most k connections. Given a list of flights (origin, destination, price), find the cheapest fare and print the itinerary. Input: first line origin and destination, second line k (max connections), third line n (number of flights), then n lines "origin destination price". Output: cheapest price and itinerary as "price: airport1 airport2 ...", or "null".