题意：
n个点，m个边，然后给出m条边的顶点和权值，其次是q次替换，每次替换一条边，给出每次替换的边的顶点和权值，然后求出这次替换的最小生成树的值;
最后要你输出:q次替换的平均值。其中n<3000，q<10000。
分析：
我们可以先求最小生成树，对于最小生成树的每一条边，我们要找到它的最佳替代边，使其价值最小。
具体实践方法：
树形dp，从每个点dfs一次，每次把i当成根，其余都是它的孩子，更新dp数组，对于i点为根的除j之外的所有的
子树中的所有点到j距离最小值。每次从一个点root开始dfs，搜索到最后一个叶子，开始看G[root][u]的大小，保证（root，u）
不是MST上的的边，那么一路返回，连接叶子节点的那条边的最佳替换边就是G[root][u]的大小，再继续返回，
此过程要看,map[root][...]的大小，其中[...]表示从叶子节点一路返回过来的点。
// File Name: 1504.cpp
// Author: Zlbing
// Created Time: 2013/6/17 19:36:53 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=;
struct Edge{
int u,v,cost;
bool operator <(const Edge &rsh)const{
return cost<rsh.cost;
}
};
vector<Edge>edges;
vector<int> mst[MAXN];
int gmst[MAXN][MAXN];
int f[MAXN];
int dp[MAXN][MAXN];
int G[MAXN][MAXN];
int n,m,Q;
int ans=;
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void kruscal()
{
ans=;
CL(gmst,);
for(int i=;i<=n;i++)f[i]=i;
for(int i=;i<m;i++)
{
Edge e=edges[i];
int fu=find(e.u);
int fv=find(e.v);
if(fu!=fv)
{
ans+=e.cost;
f[fu]=fv;
mst[e.u].push_back(e.v);
mst[e.v].push_back(e.u);
gmst[e.u][e.v]=gmst[e.v][e.u]=;
}
}
}
int dfs(int root,int u,int fa)
{
int s=INF;
for(int i=;i<mst[u].size();i++)
{
int v=mst[u][i];
if(v==fa)continue;
int tmp=dfs(root,v,u);
s=min(s,tmp);
dp[u][v]=dp[v][u]=min(dp[u][v],tmp);
}
if(root!=fa)//保证这条边不是生成树的边
s=min(s,G[root][u]);
return s;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==)break;
edges.clear();
int a,b,c;
REP(i,,n)mst[i].clear();
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
dp[i][j]=INF;
G[i][j]=INF;
}
REP(i,,m)
{
scanf("%d%d%d",&a,&b,&c);
edges.push_back((Edge){a,b,c});
G[a][b]=G[b][a]=c;
}
sort(edges.begin(),edges.end());
kruscal();
REP(i,,n-)
dfs(i,i,-);
int sum=;
scanf("%d",&Q);
REP(i,,Q)
{
scanf("%d%d%d",&a,&b,&c);
if(!gmst[a][b])
sum+=ans;
else
sum+=ans*1.0-G[a][b]+min(dp[a][b],c);
}
double s=sum/(double)Q;
printf("%.4lf\n",s);
}
return ;
}