There are n cities 1 .. n and two-way roads (a, b, c) of length c >= 1 (there may be several roads between the same pair). You must answer many queries (a, b): the length of the shortest route between a and b, or -1 if there's none.
Write shortest_routes_ii(n, roads, queries) -> list[int] returning the answers in query order.
roads = [(1, 2, 5), (1, 3, 9), (2, 3, 3)]
shortest_routes_ii(4, roads, [(1, 2), (2, 1), (3, 1), (1, 4), (4, 4)])
# [5, 5, 8, -1, 0]
Constraints: 1 <= n <= 100, up to 5,000 roads, 1 <= c <= 10^9, up to 5 * 10^4 queries. Route lengths can exceed 32 bits. A road may connect a city to itself. Running a fresh search for every query is too slow.
Show hint
With only 100 cities but tens of thousands of queries, compute the distance between every pair once, up front. One classic way builds the table by allowing one more city as a possible stop in the middle of a route at each step, which takes O(n³) in total.