dijkstra_no_heap

def dijkstra_no_heap(graph, start):
    n = len(graph)
    distance = [float('inf')] * n
    distance[start] = 0
    unvisited = set(range(n))
    path = [-1] * n
    end = 0

    min_distance = float('inf')
    min_vertex = None

    for _ in range(n):
        if min_vertex is None or min_vertex not in unvisited:
            min_distance = float('inf')
            for v in unvisited:
                if distance[v] < min_distance:
                    min_distance = distance[v]
                    min_vertex = v

        if min_distance == float('inf') or min_vertex == end:
            break

        unvisited.remove(min_vertex)

        for v, weight in graph[min_vertex]:
            if distance[min_vertex] + weight < distance[v]:
                distance[v] = distance[min_vertex] + weight
                path[v] = min_vertex

                if v in unvisited and distance[v] < min_distance:
                    min_distance = distance[v]
                    min_vertex = v

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