如果修改边权的边如果不是组成最小生成树的边，那么肯定不会有影响。
那么对于其他的边来说，就把它删了然后找到最短的替代边，和原树+修改的边权中选小的那个即可。
其实就是次小生成树的变种，只是保存每一条边删除以后的最小值罢了。

#include<iostream>
#include<string>
#include<cstdio>
#include<set>
#include<stack>
#include<list>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<fstream>using namespace std;
typedef long long ll;//ifstream cin;const int maxn = 3500,maxe = maxn * maxn,INF = 0x3f3f3f3f;int n,m;struct node{int u,v,w;bool operator < (const node &a) const {return w < a.w;}
}e[maxe];bool isedge[maxn][maxn];vector<int> r[maxn];//生成树上的边，用于dfs
vector<node> mst;//mst上的每一条边
vector<int> pl;//删边以后一棵子树上的所有点int top[maxn];
int wei[maxn][maxn];//x-y的边权
int add[maxn][maxn];//删除x-y边之后加入边的边权bool vis[maxn];int find(int x){return x == top[x] ? x : top[x] = find(top[x]);
}void dfs(int fa,int u,int ed){//寻找删边以后u所在子树上的所有点if (u == ed) return;pl.push_back(u);vis[u] = true;for(int i = 0;i < r[u].size();++i){int p = r[u][i];if (p != fa && !vis[p]) dfs(u,p,ed);}
}int kruskal(){int ans = 0;mst.clear();for(int i = 0;i < n;++i) top[i] = i,r[i].clear();int sum = 1;for(int k = 0;k < m;++k){int u = e[k].u,v = e[k].v,w = e[k].w;int fu = find(u),fv = find(v);if (fu != fv){ans += w;top[fu] = fv;isedge[u][v] = isedge[v][u] = 1;r[u].push_back(v);r[v].push_back(u);mst.push_back(e[k]);sum++;}if (sum == n){break;}}memset(add,INF,sizeof add);for(int k = 0;k < mst.size();++k){//遍历每一条边，找到删除之后加入新边的最小值int u = mst[k].u,v = mst[k].v;pl.clear();memset(vis,0,sizeof vis);dfs(u,u,v);for(int t = 0;t < m;++t){//寻找新边int x = e[t].u,y = e[t].v,w = e[t].w;if (isedge[x][y]) continue;if ((vis[x] && vis[y]) || (!vis[x] && !vis[y])) continue;add[u][v] = add[v][u] = w;break;}}return ans;
}void init(){int a,b,c;memset(isedge,0,sizeof isedge);memset(e,0,sizeof e);memset(wei,0,sizeof wei);for(int i = 0;i < m;++i){cin >> a >> b >> c;e[i] = {a,b,c};wei[a][b] = wei[b][a] = c;}sort(e,e + m);int t,ans = 0;int kru = kruskal();cin >> t;for(int k = 0;k < t;++k){cin >> a >> b >> c;if (isedge[a][b]){ans += min(kru - wei[a][b] + c,kru - wei[a][b] + add[a][b]);}else ans += kru;}printf("%.4f\n",(double)ans * 1.0 / t);
}int main(){//cin.open("in.txt");while(cin >> n >> m && n && m){init();}
}