/** *here mst means minimum spanning tree *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 mst of 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; vectormst; 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; }