Given a connected undirected graph with $n$ vertices and $m$ edges. Given $q$ queries of the form $(i,w)$, change the weight of the $i$-th edge to $w$. Find the weight of the minimum spanning tree of the graph after each query.
### Input
- The first line contains three integers $n, m, q$.
- The next $m$ lines each contain three integers $u, v, w$, representing an edge between $u$ and $v$ with weight $w$.
- The next $q$ lines each contain a query in the specified format.
### Output
- After each query, print an integer representing the weight of the minimum spanning tree.
### Constraints
- $1 \leq n \leq 2 \times 10^4$.
- $1 \leq m,q \leq 5 \times 10^4$.
- $1 \leq u \leq v \leq n$.
- $1 \leq w \leq 5 \times 10^7$.
### Example
Input:
```
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:
```
14
10
9
```