/**
*First of all, I will be taking input until the whole graph is connected, and also,
*For every query, I have to output -1.
*After getting the whole graph connected, I have to perform my first MST. 
*then I will output the mst as well.
*then I have to input every remained query and for every steps, the last added edge
*will make e cycle, and we have to remove the largest edge form the graph, which is unnecessary.. then.. output the ans it :D  
**/

#include <bits/stdc++.h>
using namespace std;

const int N = 503;

struct pii{
	int a;
	int b;
	int c;
	pii(){a = 0,b = 0,c = 0;}
	pii(int m,int n,int o){
		a = m;
		b = n;
		c = o;
	}
};bool operator<(pii a,pii b){return a.c < b.c;}
int n,pos,size,ans,parent[N],q,u,v,w;
vector<pii>mst;
pii ara[N+12];

void makeset(){for(int i = 0; i < N;i++)parent[i] = i;}
int find(int n){return n==parent[n]?n:parent[n]=find(parent[n]);}
void Union(int a,int b){ parent[find(a)] = find(b);}


int first_mst()
{
	sort(mst.begin(),mst.end());
	makeset();
	size = mst.size();
	int sum = 0;
	for(int i = 0; i < size;i++){
		if(find(mst[i].a) != find(mst[i].b)){
			Union(mst[i].a,mst[i].b);
			ara[pos++] = pii(mst[i].a,mst[i].b,mst[i].c);
			sum += mst[i].c;
		}
	}	
	return sum;
}

void mst2()
{

	size = pos;
	sort(ara,ara+size);
	makeset();
	int indx = -1;
	int sum = 0;
	for(int i  = 0; i < size;i++){
		if(find(ara[i].a) != find(ara[i].b)){
			Union(ara[i].a,ara[i].b);
			sum += ara[i].c;
		}
		else{
			indx = i;
		}
	}
	if(indx == pos-1){
		pos--;
	}
	else if(indx != -1){
		pii mm = ara[pos-1];
		ara[indx] = mm;
		pos--;
	}
	printf("%d\n",sum);
}

int main()
{
	//freopen("in.txt","r",stdin);
	int t,caseno = 0;
	scanf("%d",&t);
	while(t--){
		mst.clear();
		pos = 0;
		makeset();
		scanf("%d%d",&n,&q);
		printf("Case %d:\n",++caseno);
		int k = n;
		while(q--){
			scanf("%d%d%d",&u,&v,&w);
			mst.push_back(pii(u,v,w));
			if(find(u) != find(v)){
				k--;
				Union(u,v);
			}
			if(k == 1)break;
			printf("-1\n");
		}
		int ans = first_mst();
		printf("%d\n",ans);
		while(q--){
			scanf("%d%d%d",&u,&v,&w);
			ara[pos++] = pii(u,v,w);
			mst2();
		}
	}
	return 0;
}