import heapq


def dijkstra(graph):
    """
    Dijkstra's Algorithm for Shortest Path
    Complexity: O(V + E*logE) or O(E*logE) or O(E*logV)
                because E <= V*(V-1)/2 or E <= V*(V-1)

    We use a min heap as the priority queue. The O(V) int the coplexity
    comes from the initialization of distances.
    """
    visited = [False] * len(graph)
    distances = [float("inf")] * len(graph)
    distances[0] = 0
    priority_queue = []
    heapq.heappush(priority_queue, (0, 0))
    while priority_queue:
        min_vert = heapq.heappop(priority_queue)
        vert = min_vert[1]
        if visited[vert]:
            continue

        visited[vert] = True
        for i in range(len(graph[vert])):
            next_vert = graph[vert][i][0]-1
            next_weight = graph[vert][i][1]
            if distances[vert] + next_weight < distances[next_vert]:
                distances[next_vert] = distances[vert] + next_weight
                heapq.heappush(priority_queue, (distances[next_vert], next_vert))

    return distances