题意：

给定n个点m条边的无向图。

以下m行给出边和边权

以下Q个询问。

Q行每行给出一条边（一定是m条边中的一条）

表示改动边权。

（数据保证改动后的边权比原先的边权大）

问：改动后的最小生成树的权值是多少。

每一个询问互相独立（即每次询问都是对于原图改动）

保证没有重边。

求：全部改动后的最小生成树权值的平均值。

思路：

首先跑一个最小生成树。

求得这个MST的权值 int mst;

对于每一个询问(u.v,dis);

若(u,v) 不是MST上的边，则此时的权值就是 mst

否则我们断开树边(u,v)，然后找u点集和v点集之间的边中权值最小的边cost[u][v];

这样当前的权值就是 mst - g[u][v] + min(cost[u][v], dis);

剩下就是怎样计算cost;

MST会求得一个无根树。

我们把无根树转成以u为根时 ，对于v子树事实上是不变的。

剩下就是简单dp了

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

#include <string>

#include <iostream>

#include <queue>

#include <algorithm>

#include <cmath>

template <class T>

inline bool rd(T &ret) {

	char c; int sgn;

	if(c=getchar(),c==EOF) return 0;

	while(c!='-'&&(c<'0'||c>'9')) c=getchar();

	sgn=(c=='-')?-1:1;

	ret=(c=='-')?0:(c-'0');

	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

	ret*=sgn;

	return 1;

}

template <class T>

inline void pt(T x) {

    if (x <0) {

        putchar('-');

        x = -x;

    }

    if(x>9) pt(x/10);

    putchar(x%10+'0');

}

typedef long long ll;

using namespace std;

const ll inf = 100000000;

const int N = 3005;

ll g[N][N], d[N], mst, cost[N][N];

bool vis[N], choose[N][N];

int n, m;

vector<int> G[N];

ll dfs(int u, int fa, int src){

    ll siz = inf;

    for(int i = 0; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(v == fa)continue;

        ll tmp = dfs(v, u, src);

        siz = min(siz, tmp);

        cost[u][v] = cost[v][u] = min(cost[u][v], tmp);

    }

    if(fa != src)

        siz = min(siz, g[u][src]);

    return siz;

}

int pre[N];

void MST(){

    for(int i = 0; i < n; i++)

        for(int j = 0; j < n; j++)

            cost[i][j] = g[i][j] = inf, choose[i][j] = 0;

    while(m--){

        int u, v; ll dis; rd(u);rd(v); rd(dis);

        g[u][v] = g[v][u] = min(g[u][v], dis);

    }

    for(int i = 0; i < n; i++)

    {

        d[i] = inf;

        G[i].clear();

        vis[i] = 0;

        pre[i] = -1;

    }

    d[0] = 0;

    mst = 0;

    for(int i = 0; i < n; i++)

    {

        int pos = -1;

        for(int j = 0; j < n; j++)

            if(!vis[j] &&(pos == -1 || d[pos] > d[j]))

                pos = j;

        if(pre[pos]!=-1)

        {

            G[pos].push_back(pre[pos]);

            G[pre[pos]].push_back(pos);

            choose[pos][pre[pos]] = choose[pre[pos]][pos] = 1;

        }

        for(int j = 0; j < n; j++)

            if(d[j] > g[j][pos])

            {

                d[j] = g[j][pos];

                pre[j] = pos;

            }

        vis[pos] = 1;

        mst += d[pos];

    }

}

int main() {

    int q, u, v; ll dis;

	while(cin>>n>>m, n+m) {

        MST();

        for(int i = 0; i < n; i++)

            dfs(i, -1, i);

        rd(q);

        ll ans = 0;

        for(int i = 1; i <= q; i++) {

            rd(u); rd(v); rd(dis);

            if(choose[u][v] == false)

                ans += mst;

            else

                ans += mst - g[u][v] + min(cost[u][v], dis);

        }

        printf("%.4f\n",(double)ans/(double)q);

	}

	return 0;

}