PS country is a large country with many cities. King Louis has been racking his brains over the construction of roads between cities. Louis can build roads between certain cities, and building roads between different cities requires different costs. Louis wants to build the minimum number of roads to make all cities in the country connected. However, due to certain factors, the cost of building roads between cities changes from time to time. Louis will continuously receive messages about changes in road construction costs. He wants to know the minimum total cost to make the cities connected immediately after receiving each message. Louis has decided to ask you for help with this task.

Input

The first line of input contains three space-separated integers $N, M, Q$, representing the number of cities, the number of roads that can be built, and the number of messages received, respectively. The next $M$ lines follow. The $(i+1)$-th line contains three space-separated integers $X_i, Y_i, Z_i$ ($1 \le X_i, Y_i \le N, 0 \le Z_i \le 50000000$), indicating that the cost of building a road between city $X_i$ and city $Y_i$ is $Z_i$. The following $Q$ lines each contain two space-separated integers $K_j$ and $D_j$, indicating that the construction cost of the $K_j$-th road entered previously is modified to $D_j$.

The input data guarantees:

• 20% of the data satisfies $N \le 1000, M \le 6000, Q \le 6000$.
• 20% of the data satisfies $N \le 1000, M \le 50000, Q \le 8000$, and the modified cost will not be lower than the previous cost.
• 100% of the data satisfies $N \le 20000, M \le 50000, Q \le 50000$.

Output

The output contains $Q$ lines. The $i$-th line outputs the minimum total cost to make the cities connected after receiving the first $i$ messages.

Examples

input.txt

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

output.txt

14
10
9