import heapq


class WeightedGraph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v, w):
        if u not in self.adj:
            self.adj[u] = []
        self.adj[u].append((v, w))

    def neighbors(self, u):
        return self.adj.get(u, [])

    def shortest_distances(self, source):
        dist = {source: 0}
        pq = [(0, source)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist.get(u, float("inf")):
                continue
            for v, w in self.neighbors(u):
                nd = d + w
                if nd < dist.get(v, float("inf")):
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dist

    def shortest_path(self, source, target):
        dist = {source: 0}
        prev = {}
        pq = [(0, source)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist.get(u, float("inf")):
                continue
            for v, w in self.neighbors(u):
                nd = d + w
                if nd < dist.get(v, float("inf")):
                    dist[v] = nd
                    prev[v] = u
                    heapq.heappush(pq, (nd, v))
        if target not in dist:
            return []
        path = []
        cur = target
        while cur != source:
            path.append(cur)
            cur = prev[cur]
        path.append(source)
        path.reverse()
        return path

    def distance(self, source, target):
        dist = self.shortest_distances(source)
        return dist.get(target, float("inf"))

    def nearest(self, source, targets):
        """Return the closest target to source, tie-break by smallest node id."""
        # TODO: compute distances and pick the minimum with a deterministic tie-break
        pass