PS 国是一个拥有诸多城市的大国，国王 Louis 为城市间的道路修建可谓绞尽脑汁。Louis 可以在某些城市之间修建道路，并且在不同城市之间修建道路需要不同的花费。Louis 希望修建最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随时改变，Louis 会不断收到道路修建花费被改变的消息，他希望每收到一条消息后能立即知道使城市连通的最小总花费，Louis 决定求助于你来完成这个任务。

输入格式

输入第一行是用空格隔开的三个整数 $N,M,Q$，分别表示城市的数目、可以修建的道路的条数，以及收到的消息的个数。接下来有 $M$ 行，第 $i+1$ 行是用空格隔开的三个整数 $X_i,Y_i,Z_i$（$1\le X_i,Y_i\le N,0\le Z_i\le 50000000$），表示在城市 $X_i$ 与城市 $Y_i$ 之间修建道路的花费为 $Z_i$。紧接着的 $Q$ 行，每行是用空格隔开的两个整数 $K_j$ 和 $D_j$，表示前面输入的第 $K_j$ 条道路的修建花费被修改为 $D_j$。

输入的数据保证：

• 20% 的数据满足 $N\le 1000,M\le 6000,Q\le 6000$。
• 20% 的数据满足 $N\le 1000,M\le 50000,Q\le 8000$ 且修改后的花费不会比之前的花费低。
• 100% 的数据满足 $N\le 20000,M\le 50000,Q\le 50000$。

输出格式

输出包含 $Q$ 行，第 $i$ 行输出收到前 $i$ 条消息后使城市连通的最小总花费。

样例数据

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