Time Limit: 5 Seconds
Memory Limit: 65536 KB
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!
There 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.
For 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.