"""Guided lab: dependency-respecting deliveries on a directed weighted map."""

import heapq


def task_order(tasks, dependencies):
    outgoing = {task: set() for task in tasks}
    indegree = dict.fromkeys(tasks, 0)
    for before, after in dependencies:
        if before not in outgoing or after not in outgoing:
            raise ValueError("A dependency refers to an unknown delivery")
        if after not in outgoing[before]:
            outgoing[before].add(after)
            indegree[after] += 1
    ready = [task for task in tasks if indegree[task] == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        task = heapq.heappop(ready)
        order.append(task)
        for after in outgoing[task]:
            indegree[after] -= 1
            if indegree[after] == 0:
                heapq.heappush(ready, after)
    if len(order) != len(tasks):
        raise ValueError("Delivery dependencies contain a cycle")
    return order


def shortest_paths(adjacency, source):
    distances = [float("inf")] * len(adjacency)
    parent = [None] * len(adjacency)
    distances[source] = 0
    ready = [(0, source)]
    while ready:
        distance, node = heapq.heappop(ready)
        if distance != distances[node]:
            continue  # A cheaper route superseded this heap entry.
        for neighbor, weight in adjacency[node]:
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                parent[neighbor] = node
                heapq.heappush(ready, (candidate, neighbor))
    return distances, parent


def delivery_plan(n, roads, deliveries, dependencies, start=0):
    if n <= 0 or not 0 <= start < n:
        raise ValueError("Invalid station count or start")
    if len(set(deliveries)) != len(deliveries):
        raise ValueError("Each station has at most one delivery")
    if any(not 0 <= node < n for node in deliveries):
        raise ValueError("Unknown delivery station")
    adjacency = [[] for _ in range(n)]
    for source, target, weight in roads:
        if not 0 <= source < n or not 0 <= target < n or weight < 0:
            raise ValueError("Road endpoints must exist and weights be nonnegative")
        adjacency[source].append((target, weight))
    order = task_order(deliveries, dependencies)
    current, total, legs = start, 0, []
    for destination in order:
        distances, parents = shortest_paths(adjacency, current)
        if distances[destination] == float("inf"):
            raise ValueError(f"Delivery {destination} is unreachable from {current}")
        path, node = [], destination
        while node is not None:
            path.append(node)
            node = parents[node]
        path.reverse()
        legs.append({"from": current, "to": destination,
                     "path": path, "cost": distances[destination]})
        total += distances[destination]
        current = destination
    return {"order": order, "legs": legs, "total_cost": total}