You are given an undirected weighted graph with N vertices (numbered from 1 to N) and M edges. Your task is to process Q queries of two different types.

Query Types

Type 1

1 u v 0

Find the length of the shortest path between vertices u and v, and add this distance to a running total.

Type 2

2 u v w

An edge already exists between vertices u and v. Update the weight of this edge to w.

After processing all queries, output the final value of the running total.

Input Format

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains three integers N, M, and Q — the number of vertices, edges, and queries.
• The next M lines each contain three integers u, v, and w, representing an undirected edge between u and v with weight w.
• The next Q lines describe the queries in one of the following formats:
  • 1 u v 0
  • 2 u v w

Output Format

For each test case, print a single integer — the sum of the shortest path distances obtained from all Type 1 queries.

Explanation: Initially, the shortest distance from 1 to 4 is 3 + 4 + 2 = 9.

After updating the weight of edge (1, 4) to 5, the shortest distance from 1 to 4 becomes 5.

Finally, the shortest distance from 2 to 4 is 4 + 2 = 6.

The required sum is:

9 + 5 + 6 = 20

Note: The sample output should be 20, not 18. The provided sample output appears to be incorrect.