def shortest_path_tree(g, src, d):
    """
    Reconstruct shortest-path tree rooted at vertex src, given distance map d.
    Return tree as a map from each reachable vertex v (other than src) to the 
    edge e=(u,v) that is used to reach v from its parent u in the tree.
    """
    tree = {}
    for v in d:
        if v is not src:
            for edge in g.incident_edges(v, outgoing=False):
                u = edge.opposite(v)
                w = edge.element()
                if d[u] + w == d[v]:
                    tree[v] = edge
    return tree