405171: GYM101808 K Another Shortest Path Problem

Shortest path problems have always been a part of competitive programming, appearing in many contests all around the world. In order to keep that tradition, we created another one:

You are given an undirected connected weighted graph with N nodes and N edges, and you have to answer Q queries. Each query consists of two nodes X and Y, and you have to find the length of the shortest path between nodes X and Y.

The first line contains a single integer T, the number of test cases.

Each test case starts with a line containing two integers N and Q, the number of nodes (and edges) and the number of queries. (3 ≤ N ≤ 10⁵) (1 ≤ Q ≤ 10⁵)

Each of the following N lines contain the description of the edges. The i^th line contains 3 space-separated integers u_i, v_i, and w_i. This means that there is an undirected edge between nodes u_i and v_i, with a weight of w_i. (1 ≤ u_i, v_i ≤ N) (1 ≤ w_i ≤ 10⁵)

Then Q lines follow, the i^th line contains two integers X and Y. This means that you need to find the shortest path between nodes X and Y. (1 ≤ X, Y ≤ N)

It is guaranteed that the graph contains no self loops or multiple edges.

For each test case, and for each query, print one line containing one integer, the shortest path between X and Y.

1
6 3
1 2 2
1 3 4
2 6 3
3 4 1
3 5 10
3 6 6
1 4
2 5
3 2

5
16
6