UVA1504 Genghis Khan the Conqueror
题目描述
### 题目大意：
有一个 $n$ 个点 $m$ 条边的无向图，每条边有边权。现有 $q$ 次修改，每次将从 $u$ 到 $v$ 的边的边权改为 $w$ 。问每次修改后该图最小生成树的边权和为多少。
**请在输入 $q$ 次修改后输出每次修改后答案的平均数，答案保留四位小数。**
---
输入格式
**本题有多组数据**。
对于每组数据：
第一行两个整数 $n,m$ ，表示 $n$ 个点 $m$ 条边。
接下来 $m$ 行，每行三个整数 $u,v,w$ ，表示这条边的端点 $u,v$ 以及边权 $w$ 。
第 $m+2$ 行一个整数 $q$ ，表示修改的总数。
接下来 $q$ 行，每行三个整数 $u,v,w$ ，表示将端点为 $u,v$ 的边的边权改为 $w$ 。
输出格式
对于每组数据：
输出一个浮点数，表示每次修改后最小生成树边权和的平均数。
---
#### 样例输入：
```plain
3 3
0 1 3
0 2 2
1 2 5
3
0 2 3
1 2 6
0 1 6
0 0
```
#### 样例输出：
```plain
6.0000
```
---
#### 样例解释：
修改前三次修改后最小生成树边权和分别为5，6，7，平均数为6。
----
说明/提示
$1 \le n \leq 3000$，$1 \le m \le n^2$，$1\le q\le 10^4$。
$0 \le u,v \le n-1$，$w\le 10^7$。