You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

PS 国是一个拥有诸多城市的大国。国王 Louis 为城市的交通建设可谓绞尽脑汁。Louis 可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。

Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变。Louis 会不断得到某道路的修建代价改变的消息。他希望每得到一条消息后能立即知道使城市连通的最小花费总和。Louis 决定求助于你来完成这个任务。

输入格式

第一行包含三个整数 $n,m,q$，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。

接下来 $m$ 行，第 $i+1$ 行有三个用空格隔开的整数 $x_i,y_i,z_i$，表示在城市 $x_i$ 与城市 $y_i$ 之间修建道路的代价为 $z_i$。接下来 $q$ 行，每行包含两个数 $k,d$，表示输入的第 $k$ 个道路的修建代价修改为 $d$（即将 $z_k$ 修改为 $d$）。

输出格式

输出包含 $q$ 行，第 $i$ 行输出得知前 $i$ 条消息后使城市连通的最小花费总和。

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

14
10
9

提示

数据规模与约定

• 对于 $20\%$ 的数据，$n\le 10^3$，$m,q\le 6\times 10^3$。
• 对于另外 $20\%$ 的数据，$n\le 10^3$，$m\le 5\times 10^4$，$q\le 8\times 10^3$。修改后的代价不会比之前的代价低。
• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^4$，$1\le m,q\le 5\times 10^4$，$1\le x_i,y_i\le n$，$0\le z_i\le 5\times 10^7$。