from collections import defaultdict
import heapq

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:

	flight_map = defaultdict(list)

	for start, end, price in flights:

		fligh_map[start].append([end,price])

	heap = [(0, -1, src)] #price, stops, city

	while heap:

		cur_price, stops, cur_city = heapq.heappop(heap)

		if stops>k:
			continue

		if cur_city==dst:
			return cur_price

		for neighbor, price in flight_map[cur_city]:
			heapq.heappush(heap, (cur_price+price, stops+1, neighbor))

	return -1