1754. [HNOI 2010]城市建设

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

文件第一行包含三个整数$ N , M , Q $，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。 接下来$ M $行，第$ i + 1 $行有三个用空格隔开的整数$ X_i , Y_i   , Z_i ( 1 ≤ X_i , Y_i ≤ n , 0 ≤ Z_i ≤ 5×10^7) $，表示在城市Xi与城市Yi之间修建道路的代价为$ 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 ≤ 1000, m ≤ 6000 , Q ≤ 6000 $。
有$ 20\% $的数据，$ n ≤ 1000 , m ≤ 50000 , Q ≤ 8000 $,修改后的代价不会比之前的代价低。
对于$ 100\% $的数据, $ n ≤ 20000 , m ≤ 50000 , Q≤50000 $。