#include<bits/stdc++.h>
#define LL long long
#define N ((int)1e4 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;

//vector < pair < int , int > > bridge;

vector < pair < int , int > > edg[N];

int par[N] , deg[N] , reach[N] , dep[N], cost[N] , dsu[N] , cnt[N] ;
bool vis[N];
LL parEdge[N];

int dfs(int n , int p , int tot)
{
    reach[n] = dep[n] = dep[p] + 1;
    vis[n] = 1;
    par[n] = p;
    deg[n] = 1;
    int nodes = 1;
    for(auto adj:edg[n]){
        int a = adj.first;
        if(a == p){
            p = -1;
            continue;
        }
        else if(vis[a] == 0){
            deg[n]++;
            int cnt = dfs(a , n , tot);
            nodes += cnt;
            if(reach[a] > dep[n]){
                /// found bridge
                parEdge[a] = 1LL*cnt*(tot-cnt)*adj.second;
            }
            else parEdge[a] = 0;
            reach[n] = min(reach[n] , reach[a]);
        }
        else if(dep[a] < dep[n]){
            reach[n] = min(reach[n] , dep[a]);
        }
    }
    return nodes;
}

void Init(int n)
{
    for(int i = 1 ; i <= n ; i++){
        vis[i] = 0;
        edg[i].clear();
        dsu[i] = i;
        cnt[i] = 1;
    }

}

int FindRoot(int n)
{
    if(n == dsu[n]) return n;
    return dsu[n] = FindRoot(dsu[n]);
}

void Connect(int a , int b)
{
    int rootA = FindRoot(a) , rootB = FindRoot(b);
    if(rootA != rootB){
        dsu[rootB] = rootA;
        cnt[rootA] += cnt[rootB];
    }
}

bool Assign(int n , LL MaxCost)
{
    vector < LL > arr(n+1);
    vector < int > Deg(n+1);
    for(int i = 1 ; i <= n ; i++) arr[i] = cost[i] , Deg[i] = deg[i];
    queue < int > leaf;
    for(int i = 1 ; i <= n ; i++) if(Deg[i] == 1 && FindRoot(i) != i) leaf.push(i);
    while(!leaf.empty()){
        int cur = leaf.front();
        leaf.pop();
        int p = par[cur];
        LL w = parEdge[cur];
        //cout<<cur<<" "<<p<<" "<<w<<endl;
        if(arr[cur] + w <= MaxCost) arr[cur] += w;
        else if(p > 0 && arr[p] + w <= MaxCost) arr[p] += w;
        else return false;
        Deg[p]--;
        if(p > 0 && Deg[p] == 1) leaf.push(p);
    }
    return true;
}

void Solve(int caseNo)
{
    int n , m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++) cin>>cost[i];
    Init(n);
    while(m--){
        int a, b , w;
        cin>>a>>b>>w;
        edg[a].push_back({b,w});
        edg[b].push_back({a,w});
        Connect(a,b);
    }
    for(int i = 1 ; i <= n ; i++){
        if(FindRoot(i) == i) dfs(i , 0 , cnt[i]);
    }
    LL lef = 0 , rig = 1e17;
    while(lef < rig){
        LL mid = (lef + rig) >> 1;
        if(Assign(n , mid)) rig = mid;
        else lef = mid+1;
    }
    cout<<"Case "<<caseNo<<": "<<lef<<endl;
}

int main(){
    /// problem: https://lightoj.com/problem/reduce-cost
    fastio;
    int t , caseNo = 1;
    cin>>t;
    while(t--){
        Solve(caseNo++);
    }
    return 0;
}