

Traffic Network in NumazuTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1179 Accepted Submission(s): 490 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$ spaceseparated 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
Sample Output
Source  
