def dijkstra(n, e): 
    from heapq import heappush, heappop
    q = [[0, 0]]
    dist = [10 ** 8] * n 
    while q:
        d, u = heappop(q)
        if dist[u] != 10 ** 8: continue 
        dist[u] = d 
        for dv, v in e[u]:
            if dist[v] == 10 ** 8:
                heappush(q, [d + dv, v])
    return dist