
ZOJ Problem Set  3742
Now, Bellywhite is doing his algorithm course homework. Here is the homework problem: Given a graph with N vertices (numbered from 1 to N) and M undirected weighted edges, you should finish Q operations. Each operation is one of following two types:
Bellywhite is trapped in it nearly a week, so he turn to you, the cleverest one on earth! InputThere are multiple cases. There is an empty line between two cases. The first line of each case consists of three integers N, M, Q (1 ≤ N ≤ 50000, 0 ≤ M ≤ 50000, 0 ≤ Q ≤ 50000), as described above. There are M lines followed. Each line consists of three integers a, b, c (1 ≤ a, b ≤ N, a ≠ b, 50000 ≤ c ≤ 50000), which mean there is an edge between vertex a and b, weighted c (there might be multiple edges between two vertices). Then, there are Q lines followed. Each line is either operation form described above. See samples for details. OutputFor each case, output an integer for each query operation (Type 1) meaning the sum of edges weights queried, in one line. Please output an empty line between two cases. Sample Input4 6 5 1 2 1 1 3 1 1 4 1 2 3 1 2 4 1 3 4 1 Q A C 1 Q + C 3 Q  2 1 3 1 2 3 Q A C 1 Q  Sample Output6 3 4 3 0 Author: YU, Xiaoyao Contest: ZOJ Monthly, December 2013 