In this problem you are required to answer one of two queries given an undirected weighted connected graph.

1 u - Find the longest direct path starting from u

2 u - Find the shortest direct path starting from u

A path between u and v is direct if it has the shortest length among all paths between u and v, where u and v are different nodes.

Note: The author does not have an intended solution involving a link cut tree data structure.

Input Specification

The first line will contain two integers ~N~ and ~M~ ~({2 \le N \le 5000}~, ~{1 \le M \le 10^4})~, the number of nodes, and the number of edges, respectively.

The next ~M~ lines will contain three integers ~u_i~, ~v_i~ ~({1 \le u_i, v_i \le N})~, and ~w_i~ ~({1 \le w_i \le 10^5})~, indicating there is an edge between ~u_i~ and ~v_i~ with length ~w_i~.

The next line will contain one integer ~Q~ ~({1 \le Q \le 10^5})~, the number of queries.

The next ~Q~ lines will contain a query of the form described above.

There will be no self-loops or duplicate edges.

Output specification

One integer per line answering the queries described above in the order of the input.

Sample Input 1

4 4
1 3 1
2 1 3
4 3 5
1 4 7
6
1 3
2 1
1 2
2 2
1 1
2 3

Sample Output 1

5
1
9
3
6
1

Sample Input 2

3 3
2 1 5
3 1 1
3 2 9
5
1 2
2 2
1 3
2 3
2 1

Sample Output 2

6
5
6
1
1