class IndexMinPQ:

    def __init__(self, n):
        self.vals = [None for i in range(n)]
        self.pm = [-1 for i in range(n)] # position map
        self.pq = [-1 for i in range(n)] # priority queue
        self.n = 0

    def less(self, i, j):
        return self.vals[self.pq[i]] < self.vals[self.pq[j]]

    def swap(self, i, j):
        self.pm[self.pq[i]], self.pm[self.pq[j]] = self.pm[self.pq[j]], self.pm[self.pq[i]]
        self.pq[i], self.pq[j] = self.pq[j], self.pq[i]

    def swim(self, index):
        parent = (index - 1) // 2
        if index > 0 and self.less(index, parent):
            self.swap(index, parent)
            self.swim(parent)

    def sink(self, index):
        left = 2 * index + 1
        right = 2 * index + 2
        child = left
        if right < self.n and self.less(right, left):
            child = right
        if left >= self.n or self.less(index, child):
            return
        self.swap(index, child)
        self.sink(child)

    def insert(self, key, val):
        if self.contains(key):
            raise ValueError("The supplied key is already in the priority queue. Try using update method.")
        self.vals[key] = val
        self.pm[key] = self.n
        self.pq[self.n] = key
        self.swim(self.n)
        self.n += 1

    def update(self, key, val):
        if self.empty():
            raise ValueError("The priority queue is empty.")
        oldval = self.vals[key]
        self.vals[key] = val
        index = self.pm[key]
        self.sink(index)
        self.swim(index)
        return oldval

    def delete(self, key):
        index = self.pm[key]
        self.n -= 1
        self.swap(index, self.n)
        self.vals[key] = None
        self.pq[self.n] = -1
        self.pm[key] = -1
        self.sink(index)
        self.swim(index)

    def decrease(self, key, val):
        if self.empty():
            raise ValueError("The priority queue is empty.")
        if val < self.vals[key]:
            self.vals[key] = val
            self.swim(self.pm[key])

    def increase(self, key, val):
        if self.empty():
            raise ValueError("The priority queue is empty.")
        if self.vals[key] < val:
            self.vals[key] = val
            self.sink(self.pm[key])

    def del_min(self):
        if self.empty():
            return None
        key = self.get_min_key()
        self.delete(key)
        return key

    def value_of(self, key):
        return self.vals[key]

    def get_min_val(self):
        return self.vals[self.pq[0]]

    def get_min_key(self):
        return self.pq[0]

    def contains(self, key):
        return self.pm[key] != -1

    def empty(self):
        return self.n == 0

    def size(self):
        return self.n

    def __str__(self):
        out = ""
        out += str([self.pq[i] for i in range(self.n)])
        out += "\n"
        #out += str(self.pm)
        #out += "\n"
        l = lambda i: self.vals[self.pq[i]] if self.pq[i] != -1 else None
        out += str([l(i) for i in range(self.n)])
        #out += str(self.vals)
        return out

class BaseSPT:

    def __init__(self, g, s):
        self.s = s
        self.distance = [float("inf") for i in range(g.v())]
        self.path = [None for i in range(g.v())]

    def source(self):
        return self.s

    def dist(self, v):
        return self.distance[v]

    def path_to(self, v):
        path = gs.Stack()
        e = self.path[v]
        while e is not None:
            path.push(e)
            e = self.path[e.from_v()]
        return path

    def relax(self, e):
        v, w = e.from_v(), e.to_v()
        if self.distance[w] > self.distance[v] + e.weight():
            self.distance[w] = self.distance[v] + e.weight()
            self.path[w] = e

    def __str__(self):
        out = ""
        out += str(self.distance)
        out += "\n"
        out += str(self.path)
        return out

    def __repr__(self):
        return self.__Str__()


class DijkstrasSPT(BaseSPT):

    def __init__(self, g, s):
        super().__init__(g, s)
        self.q = IndexMinPQ(g.v())
        self.search(g, s)

    def search(self, g, s):
        self.distance[s] = 0.0
        self.q.insert(s, 0.0)
        while not self.q.empty():
            v = self.q.del_min()
            for e in g.adj(v):
                self.relax(e)

    def relax(self, e):
        v, w = e.from_v(), e.to_v()
        if self.distance[w] > self.distance[v] + e.weight():
            self.distance[w] = self.distance[v] + e.weight()
            self.path[w] = e
            if self.q.contains(w):
                self.q.decrease(w, self.distance[w])
            else:
                self.q.insert(w, self.distance[w])