题意：n个城市(n <= 10000)， 有m条边（m <= 40000），每一个城市有一个维护费用Cost（i），除此之外，每条边的维修费用为去掉该边后不能通信的城市对数与边权的积。这个费用要加到这条边的两端城市的某一个，问你全部城市的最大费用的最小值。、

思路：首先边的费用能够通过Tarjan求桥之后求得(利用桥的性质)，然后就是二分答案了！对于每一个点，假设有个儿子不能维护。那么不可行，否则。试着让儿子去维护边权，假设不可行，仅仅能让父亲承担。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long LL;

const int maxn = 10000+10;

const int maxm = 40000+10;

LL cost[maxn];

int head[maxn];

int n,m;

int dfn[maxn],lown[maxn];

bool CanE[maxn];

int cnt[maxm];

LL ans;

int nume,dfs_clock;

bool vis[maxn];

bool isBridge[maxm];

vector<int> sta;

struct edge{

    int u,v,w,nxt;

}e[maxm];

void Tarjan(int u,int fa) {

    lown[u] = dfn[u] = dfs_clock++;

    sta.push_back(u);

    for(int i = head[u]; i ; i = e[i].nxt) {

        int v = e[i].v;

        if(v==fa) continue;

        if(!dfn[v]) {

            Tarjan(v,u);

            lown[u] = min(lown[u],lown[v]);

            if(lown[v] > dfn[u]) {

                isBridge[i] = isBridge[i^1] = true;

                cnt[i] = cnt[i^1] = dfs_clock-dfn[v];

            }

        }else {

            lown[u] = min(lown[u],dfn[v]);

        }

    }

}

bool dfs(int u,LL s,LL x) {

    vis[u] = true;

    LL ts = cost[u];

    int sz = sta.size();

    for(int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].v, w = e[i].w;

        if(isBridge[i] && !vis[v]) {

            LL tmp = (LL)w*cnt[i]*(sz-cnt[i]);

            if(!dfs(v,tmp,x)) return false;

            if(!CanE[v]) ts += tmp;

        }

    }

    if(ts > x) return false;

    if(ts+s <= x)  CanE[u] = true;

    return true;

}

bool can(LL x) {

    int len = sta.size();

    memset(CanE,false,sizeof CanE);

    for(int i = 0; i < len; i++) vis[sta[i]] = false;

    for(int i = 0; i < len; i++) {

        int t = sta[i];

        if(vis[t]) continue;

        if(!dfs(t,0,x)) return false;

    }

    return true;

}

void init() {

    nume = 1;

    ans = 0;

    dfs_clock = 1;

    memset(head,0,sizeof head);

    memset(isBridge,false,sizeof isBridge);

    memset(vis,false,sizeof vis);

    memset(dfn,0,sizeof dfn);

    memset(lown,0,sizeof lown);

    memset(CanE,false,sizeof CanE);

    sta.clear();

}

void addedge(int u,int v,int w) {

    e[++nume].nxt = head[u];

    e[nume].u = u;

    e[nume].v = v;

    e[nume].w = w;

    head[u] = nume;

}

void solve() {

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

        if(!dfn[i]) {

            sta.clear();

            Tarjan(i,-1);

            LL L = ans,R = 1e10;

            while(L <= R) {

                LL mid = (L+R)/2;

                if(can(mid)) {

                    R = mid-1;

                }else{

                    L = mid+1;

                }

            }

            ans = max(ans,L);

        }

    }

    printf("%lld\n",ans);

}

int main(){

    int ncase,T=1;

    cin >> ncase;

    while(ncase--) {

        init();

        scanf("%d%d",&n,&m);

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

            scanf("%lld",&cost[i]);

            ans = max(ans,cost[i]);

        }

        for(int i = 0; i < m; i++) {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            addedge(a,b,c);

            addedge(b,a,c);

        }

        printf("Case %d: ",T++);

        solve();

    }

    return 0;

}