import heapq

def cheapest_flight(flights, start, end):
    graph = {}

    for a, b, cost in flights:
        if a not in graph:
            graph[a] = []
        graph[a].append((b, cost))

    INF = 10**9
    dist = {}
    for a, b, _ in flights:
        dist[a] = INF
        dist[b] = INF

    dist[start] = 0
    pq = [(0, start)]

    while pq:
        cur_cost, cur = heapq.heappop(pq)

        if cur == end:
            return cur_cost

        if cur_cost > dist[cur]:
            continue

        if cur in graph:
            for next_city, price in graph[cur]:
                new_cost = cur_cost + price
                if new_cost < dist[next_city]:
                    dist[next_city] = new_cost
                    heapq.heappush(pq, (new_cost, next_city))

    return dist[end]


flights = [[0,1,100], [1,2,600], [0,2,500]]
print(cheapest_flight(flights, 0, 2))