K. Another Shortest Path Problem
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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 ≤ 105) (1 ≤ Q ≤ 105)

Each of the following N lines contain the description of the edges. The ith line contains 3 space-separated integers ui, vi, and wi. This means that there is an undirected edge between nodes ui and vi, with a weight of wi. (1 ≤ ui, vi ≤ N) (1 ≤ wi ≤ 105)

Then Q lines follow, the ith 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.

Output

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

Example
Input
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
Output
5
16
6