dijkstra

from heapq import heappush, heappop

def dijkstra(graph, start):
    n = len(graph)
    distance = [float('inf')] * n
    distance[start] = 0
    queue = [(0, start)]
    visited = [False] * n
    path = [-1] * n
    end = 0

    while queue:
        dist, current = heappop(queue)

        if visited[current]:
            continue
        visited[current] = True

        if current == end:
            break

        for neighbor, weight in graph[current]:
            if dist + weight < distance[neighbor]:
                path[neighbor] = current
                distance[neighbor] = dist + weight
                heappush(queue, (distance[neighbor], neighbor))

    final_path = []
    current = end
    while current != -1:
        final_path.append(current + 1)
        current = path[current]
    return distance[end], final_path[::-1]