#include<bits/stdc++.h>
using namespace std;
const int N=210;
struct node {
	int l,r,w;
} a[N*N];
int n,m,p[N],cnt;
int find(int x) {
	if(p[x]!=x) return p[x]=find(p[x]);
	return p[x];
}
bool cmp(node a,node b) {
	return a.w<b.w;
}
int kruskal() {
	for(int i=1; i<=n; i++) p[i]=i;
	int ans=0,num=0;
	for(int i=1; i<=cnt; i++) {
		int pa=find(a[i].l),pb=find(a[i].r);
		if(pa!=pb) {
			p[pa]=pb;
			ans+=a[i].w;
			num++;
		} else {
			swap(a[i],a[cnt]);
			cnt--;
			i--;
		}
	}
	if(num==n-1) return ans;
	return -1;
}
int main() {
	int t;
	cin>>t;
	for(int i=1; i<=t; i++) {
		printf("Case %d:\n",i);
		cin>>n>>m;
		cnt=0;
		for(int i=1; i<=m; i++) {
			int l,r,w;
			cin>>l>>r>>w;
			cnt++;
			a[cnt]= {l,r,w};
			sort(a+1,a+cnt+1,cmp);
			cout<<kruskal()<<endl;
		}
	}
	return 0;
}