#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define MP(i,j) make_pair(i,j)

const int MAXN=10010;

typedef long long ll;
typedef pair<int,int> PII;
typedef pair<int,ll> PII2;

int dfn[MAXN],low[MAXN],st[MAXN],top;
int tot,hash[MAXN],num[MAXN],hp[MAXN],newn,bo,edge[MAXN];
vector <pair<int, int > > keyE;
vector <int>  keyV;
vector <PII> E[MAXN];
vector <PII> EE[MAXN];
vector<long long> valueE;
ll tp;

int tarjan(int now, int cnt){
	int part=(cnt>1);
	st[top++]=now;
	dfn[now]=low[now]=cnt;
	int cv=1;
	for (int ii=E[now].size()-1;ii>=0;--ii){
		int i=E[now][ii].first;
		if (!dfn[i]){
			int x=tarjan(i,cnt+1);
			cv += x;
			low[now]=min(low[now],low[i]);
			if (low[i]>dfn[now]){
				keyE.push_back(MP(now,i));
				
				ll len=E[now][ii].second;
				len *= (ll)x * (ll)(num[hash[i]]-x);
				tp+=len;
				valueE.push_back(len);
			}
		} else if (dfn[i]!=dfn[now]-1)
			low[now]=min(low[now],dfn[i]);
		
	
	}
	return cv;
}


void ArtEdge_ArtVertex_Components(int N){
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	keyE.clear();
	keyV.clear();
	valueE.clear();
	for (int i=top=0;i<N;i++)
		if (!dfn[i])
			tarjan(i,1);
}

void dfs(int v){
	hash[v]=tot;
	num[tot]++;
	for (int ii=E[v].size()-1;ii>=0;--ii){
		int i=E[v][ii].first;
		if (!hash[i]) dfs(i);
	}
}

int a[MAXN];
int n,m;
ll b[MAXN],c[MAXN];
map<int,int> hh;

void work(int u,ll k){
	hp[u]=1;
	if (EE[u].size()==1){
		if (b[u]+valueE[EE[u][0].second]<=k){
			edge[EE[u][0].second]=1;
			b[u]+=valueE[EE[u][0].second];
		}
		return ;
	}
	for (int i=0;i<EE[u].size();i++){
		int v=EE[u][i].first;
		if (!hp[v]){
           work(v,k);
		   if (edge[EE[u][i].second]==0){
			  if (b[v]+valueE[EE[u][i].second]<=k){
			     edge[EE[u][i].second]=1;
			     b[v]+=valueE[EE[u][i].second];
			     continue;
              }
			   
		   }
		   if (edge[EE[u][i].second]==0){
			if (b[u]+valueE[EE[u][i].second]<=k){
			edge[EE[u][i].second]=1;
			b[u]+=valueE[EE[u][i].second];
			}
		  }
		  
        }
	}
}

int check(ll k){
	memset(hp,0,sizeof(hp));
	memset(edge,0,sizeof(edge));
	bo=1;
	for (int i=1;i<=newn;i++) b[i]=c[i];
	for (int i=1;i<=newn;i++)
		if (!hp[i])
			work(i,k);
	for (int i=0;i<valueE.size();i++)
		if (edge[i]==0) bo=0;

    return bo;
}

int main(){
	freopen("G.in", "r", stdin);
	freopen("G.out", "w", stdout);
	int t;
	scanf("%d", &t);
	for (int ti = 1; ti <= t; ti ++){
		scanf("%d%d",&n,&m);
		
		ll ans=0;
		tp=0;
		for (int i=0;i<=n;i++){
	        c[i]=0;
			E[i].clear();
			EE[i].clear();
        }
        for (int i=0;i<n;i++){
			scanf("%d",&a[i]);
            ans=max(ans,(ll)a[i]);
			tp+=(ll)a[i];
		}
		for (int i=0;i<m;i++){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			E[x-1].push_back(MP(y-1,z));
			E[y-1].push_back(MP(x-1,z));
		}
		
		tot=0;
		memset(hash,0,sizeof(hash));
		memset(num,0,sizeof(num));
		for (int i=0;i<n;i++)
			if (!hash[i]){
				tot++;			
				dfs(i);
			}
			
		
		ArtEdge_ArtVertex_Components(n);
		//cout << keyE.size()<<" "<<valueE.size()<<endl;

		hh.clear();
		newn=0;
		for (int i=0;i<keyE.size();i++){
			if (hh[keyE[i].first]==0){
				newn++;
				hh[keyE[i].first]=newn;
			}
			if (hh[keyE[i].second]==0){
				newn++;
				hh[keyE[i].second]=newn;
			}
			int x=hh[keyE[i].first];
			int y=hh[keyE[i].second];
			EE[x].push_back(MP(y,i));
			EE[y].push_back(MP(x,i));
			c[x]=(ll)a[keyE[i].first];
			c[y]=(ll)a[keyE[i].second];
	
		ll l=0;
		ll r=tp;
		while (l+1<r){
			//cout << l <<" "<<r<<endl;
			ll mid=(l+r)/2;
			if (check(mid)) r=mid;
				else l=mid;
		}
		ans = max(r,ans);
		printf("Case %d: %lld\n",ti,ans);
	}
	
	return 0;
}