import heapq

def dijkstra(adj_list, start):
    dist = {node: float('inf') for node in adj_list}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, weight in adj_list[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    return dist

def build_map(overpass, west, east):
    w1, w2 = overpass
    map = {}
    for i, station in enumerate(west):
        if station == w1:
            map[(w1, i)] = 1
        elif station == w2:
            map[(w2, i)] = 1
        else:
            map[(w1, i)] = 2
            map[(w2, i)] = 2
    for i, station in enumerate(east):
        if station == w1:
            map[(w1, W+i)] = 1
        elif station == w2:
            map[(w2, W+i)] = 1
        else:
            map[(w1, W+i)] = 2
            map[(w2, W+i)] = 2
    for i, station in enumerate(west[:-1]):
        map[(station, i+1)] = 1
        map[(i+1, station)] = 1
    for i, station in enumerate(east[:-1]):
        map[(station+W, W+i+1)] = 1
        map[(W+i+1, station+W)] = 1
    dist = {}
    for i, s1 in enumerate(west+east):
        for j, s2 in enumerate(west+east):
            if i == j:
                dist[(s1, s2)] = 0
            elif (s1, s2) in map:
                dist[(s1, s