def BellmanFord(edges, start):
    """Return a dictionary of distances, one per vertex

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: the source vertex from which distances are measured

    Each edge list shows the edges out from a vertex as a list
    of (weight, destination) pairs.

    Each vertex should be a key in edges, even with an empty list."""

    d = {}  # d[v] is current best known distance to v
    for v in edges:
        d[v] = float('inf')
    d[start] = 0
    for i in range(len(edges)-1):  # len(edges) is the number of vertices
        for v0 in edges: # origin vertex of some edges
            for w, v1 in edges[v0]: # weight and destination vertex
                d1 = d[v0] + w
                if d1 < d[v1]:
                    d[v1] = d1
    for v0 in edges: # origin vertex of some edges
        for w, v1 in edges[v0]: # weight and destination vertex
            d1 = d[v0] + w
            if d1 < d[v1]:
                raise ValueError("Negative weight cycle in the graph")
    return d
    
from SkipList import SkipList

def Dijkstra(edges, start):
    """Return a dictionary of distances, one per vertex

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: the source vertex from which distances are measured

    Each edge list shows the edges out from a vertex as a list
    of (weight, destination) pairs.

    Each vertex should be a key in edges, even with an empty list.

    All weights must be nonnegative."""

    d = {}  # d[v] is current best known distance to v
    for v in edges:
        d[v] = float('inf')
    d[start] = 0
    frontier = SkipList() # key: (d[v], v), value: None
    frontier[d[start], start] = None
    while len(frontier) != 0:
        (minD, minV), n = frontier.min()
        del frontier[minD, minV]
        for w, v1 in edges[minV]:
            d1 = d[minV] + w
            if d1 < d[v1]:
                if (d[v1], v1) in frontier:
                    del frontier[d[v1], v1]
                frontier[d1, v1] = None
                d[v1] = d1
    return d