def MST_Prim(G, r):
    Q = list(G.keys())

    key = {u: float('inf') for u in G}
    pi = {u: None for u in G}

    key[r] = 0

    while Q:
        u = min(Q, key=lambda x: key[x])
        Q.remove(u)

        for v, w in G[u]:
            if v in Q and w < key[v]:
                pi[v] = u
                key[v] = w

    return pi


# Example
G = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (3, 8), (4, 5)],
    2: [(1, 3), (4, 7)],
    3: [(0, 6), (1, 8), (4, 9)],
    4: [(1, 5), (2, 7), (3, 9)]
}

print(MST_Prim(G, 0))