Traffic Network in Numazu

Problem Description

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$.

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 \leq N \leq 10^5) (1 \leq Q \leq 10^5)$
Each of the following $N$ lines contain the description of the edges. The $i_{th}$ line 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 \leq u_i, v_i \leq N) (1 \leq w_i \leq 10^5)$
Then $Q$ lines follow, the $i_{th}$ line contains $3$ integers $OP$, $X$ and $Y$. The meaning has been described above.$(0 \leq OP \leq 1) (1 \leq X \leq 10^5) (1 \leq Y \leq 10^5)$
It is guaranteed that the graph contains no self loops or multiple edges.

Output

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$.

Sample Input

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

Sample Output

5

6

6

6

Source

2018 Multi-University Training Contest 7