All-Pairs Shortest Path Queries

You are given an undirected weighted graph with n nodes labeled 1 to n, described by an array edges, where edges[i] = [a, b, c] is a two-way connection between nodes a and b (a != b) of length c. Multiple connections may exist between the same pair of nodes.

You are also given an array queries, where each queries[i] = [a, b] asks for the length of the shortest route between nodes a and b (possibly a = b).

Return an array with one answer per query, in order: the shortest route length, or -1 if no route exists.

Examples

Example 1

Input: n = 4, edges = [[1,2,5],[1,3,9],[2,3,3]], queries = [[1,2],[2,1],[1,3],[1,4],[3,2]]
Output: [5,5,8,-1,3]
Explanation: The shortest route from 1 to 3 goes through node 2 with length 5 + 3 = 8, cheaper than the direct connection of length 9. Node 4 has no connections, so [1,4] answers -1. Routes are symmetric: [1,2] and [2,1] both answer 5.