Traffic Network in Numazu

Chika is elected mayor of Numazu. She needs to manage the traffic in this city. To manage the traffic is too hard for her. So she needs your help.
You are given the map of the city —— an undirected connected weighted graph with N nodes and N edges, and you have to finish Q missions. Each mission consists of 3 integers OP, X and Y.
When OP=0, you need to modify the weight of the X_th edge to Y.
When OP=1, you need to calculate the length of the shortest path from node X to node 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≤105)(1≤Q≤105)

Each of the following N lines contain the description of the edges. The i_thline represents the i_th edge, which 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,vi≤N)(1≤wi≤105))}

For each test case, and for each mission whose OP=1, print one line containing one integer, the length of the shortest path between X and Y.

2
5 5
1 2 3
2 3 5
2 4 5
2 5 1
4 3 3
0 1 5
1 3 2
1 5 4
0 5 4
1 5 1
5 3
1 2 3
1 3 2
3 4 4
4 5 5
2 5 5
0 1 3
0 4 1
1 1 4

5
6
6
6