graph = {
    "Aldgate East": {
        "Liverpool Street": 4,
        "Tower Hill": 2
    },
    "Baker Street": {
        "Bond Street": 2,
        "Edgware Road": 3,
        "Euston Square": 5,
        "Oxford Circus": 4
    },
    "Bank": {
        "Blackfriars": 4,
        "Holborn": 5,
        "Liverpool Street": 2,
        "London Bridge": 3,
        "Moorgate": 1,
        "Tower Hill": 2
    },
    "Blackfriars": {
        "Bank": 4,
        "Embankment": 4
    },
    "Bond Street": {
        "Baker Street": 2,
        "Green Park": 2,
        "Notting Hill Gate": 7,
        "Oxford Circus": 1
    },
    "Charing Cross": {
        "Embankment": 1,
        "Leicester Square": 2,
        "Piccadilly Circus": 2
    },
    "Edgware Road": {
        "Baker Street": 3,
        "Paddington": 3
    },
    "Elephant & Castle": {
        "London Bridge": 3,
        "Waterloo": 4
    },
    "Embankment": {
        "Blackfriars": 4,
        "Charing Cross": 1,
        "Westminster": 2
    },
    "Euston Square": {
        "Baker Street": 5,
        "Kings Cross": 2
    },
    "Green Park": {
        "Bond Street": 2,
        "Oxford Circus": 2,
        "Piccadilly Circus": 1,
        "South Kensington": 7,
        "Victoria": 2,
        "Westminster": 3
    },
    "High Street Kensington": {
        "Notting Hill Gate": 3,
        "South Kensington": 5
    },
    "Holborn": {
        "Bank": 5,
        "Kings Cross": 4,
        "Leicester Square": 2,
        "Tottenham Court Road": 2
    },
    "Kings Cross": {
        "Euston Square": 2,
        "Holborn": 4,
        "Moorgate": 6,
        "Old Street": 6,
        "Warren Street": 3
    },
    "Leicester Square": {
        "Charing Cross": 2,
        "Holborn": 2,
        "Piccadilly Circus": 2,
        "Tottenham Court Road": 1
    },
    "Liverpool Street": {
        "Aldgate East": 4,
        "Bank": 2,
        "Moorgate": 2,
        "Tower Hill": 6
    },
    "London Bridge": {
        "Bank": 3,
        "Elephant & Castle": 3,
        "Waterloo": 4
    },
    "Moorgate": {
        "Bank": 3,
        "Kings Cross": 6,
        "Liverpool Street": 2,
        "Old Street": 1
    },
    "Notting Hill Gate": {
        "Bond Street": 7,
        "Paddington": 4,
        "High Street Kensington": 3
    },
    "Old Street": {
        "Kings Cross": 6,
        "Moorgate": 1
    },
    "Oxford Circus": {
        "Baker Street": 4,
        "Bond Street": 1,
        "Green Park": 2,
        "Piccadilly Circus": 2,
        "Tottenham Court Road": 2,
        "Warren Street": 2
    },
    "Paddington": {
        "Edgware Road": 3,
        "Notting Hill Gate": 4
    },
    "Piccadilly Circus": {
        "Charing Cross": 2,
        "Green Park": 1,
        "Leicester Square": 2,
        "Oxford Circus": 2
    },
    "South Kensington": {
        "Green Park": 7,
        "High Street Kensington": 5,
        "Victoria": 4
    },
    "Tottenham Court Road": {
        "Holborn": 2,
        "Leicester Square": 1,
        "Oxford Circus": 2,
        "Warren Street": 3
    },
    "Tower Hill": {
        "Aldgate East": 2,
        "Bank": 2,
        "Liverpool Street": 6
    },
    "Victoria": {
        "Green Park": 2,
        "South Kensington": 4,
        "Westminster": 4
    },
    "Warren Street": {
        "Kings Cross": 3,
        "Oxford Circus": 2,
        "Tottenham Court Road": 3
    },
    "Waterloo": {
        "Elephant & Castle": 4,
        "Embankment": 2,
        "London Bridge": 4,
        "Westminster": 2
    },
    "Westminster": {
        "Embankment": 2,
        "Green Park": 3,
        "Victoria": 4,
        "Waterloo": 2
    }
}

def dijkstra(graph, origin, destination):
    visited = []
    distance = {}
    predecessor = {}
    current = origin
    predecessor[current] = None
    distance[current] = 0
    
    while (len(visited) != len(graph)):
        visited.append(current)
        for adjSta in graph[current]:
            if adjSta not in visited:
                newDist = distance[current] + graph[current][adjSta]
                if adjSta in distance:
                    if newDist < distance[adjSta]:
                        distance[adjSta] = newDist
                        predecessor[adjSta] = current
                else:
                    distance[adjSta] = newDist
                    predecessor[adjSta] = current
        min = float("inf")
        for station in distance:
            if (station not in visited) and (distance[station] < min):
                min = distance[station]
                current = station
    
    path = []
    nextStation = destination
    while nextStation != None:
        path.append(nextStation)
        nextStation = predecessor[nextStation]
    path.reverse()
    print path
    print "This journey takes", distance[destination], "minute(s)."

if __name__ == "__main__":
    origin = raw_input("Starting station: ")
    destination = raw_input("Finishing station: ")
    dijkstra(graph, origin, destination)