F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Traffic Network in Numazu

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

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 20:28:21, Gzip enabled