class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        #Simple BFS + prune

        #Contruct weighted graph
        EdgeDict = {}
        for edge in flights:
            parent = edge[0]
            child = edge[1]
            cost = edge[2]

            if parent not in EdgeDict:
                EdgeDict[parent] = [(child, cost)]
            else:
                EdgeDict[parent].append((child, cost))

        #BFS
        Q = collections.deque([(src,0)])
        MinRes = sys.maxsize
        stop = 0
        while Q:
            n = len(Q)
            stop += 1

            for _ in range(n):
                node = Q.popleft()
                parent = node[0]
                precost = node[1]

                if parent not in EdgeDict:
                    continue

                for childNode in EdgeDict[parent]:
                    child, cost = childNode[0], childNode[1]
                    if child == dst:
                        MinRes = min(MinRes, cost+precost)
                        #res_set.append(cost + precost)
                    else:
                        if cost+precost > MinRes:
                            continue
                        Q.append((child, precost+cost))

            if stop == K+1:
                break

        if MinRes == sys.maxsize:
            return -1
        return MinRes