#include <bits/stdc++.h>
#define PI acos(-1)
using namespace std;
#define MX 10001
int parent[MX];
struct edge
{
int u;
int v;
int w;
};
vector < edge > v;
vector<int>edges;
int secondmst[202],xx=0;
bool flag1,flag2;
bool comp(edge x,edge y)
{
if(x.w<y.w)return true;
else
return false;
}
int Find(int x)
{
if(parent[x]==x)return x;
parent[x]=Find(parent[x]);
return parent[x];
}
int mst(int n)
{
sort(v.begin(),v.end(),comp);
for(int i=1; i<=n; i++)parent[i]=i;
int c=0,ans=0,l=v.size();
if(l==0)flag1=true;
for(int i=0; i<l; i++)
{
int p=Find(v[i].u);
int q=Find(v[i].v);
if(p!=q)
{
edges.push_back(i);
parent[p]=q;
++c;
ans += v[i].w;
if(c==n-1)
{
flag1=true;
break;
}
}
}
return ans;
}
int secondBestMst(int n)
{
int best2=INT_MAX,c=0;
int len=edges.size();
for(int k=0; k<len; k++)
{
for(int i=1; i<=n; i++)
{
parent[i]=i;
}
int s=0;
c=0;
for(int i=0; i<v.size(); i++)
{
if(edges[k]==i)continue;
int p=Find(v[i].u);
int q=Find(v[i].v);
if(p!=q)
{
parent[p]=q;
c++;
s += v[i].w;
if(c==n-1)
{
if(best2>s)
{
best2=s;
secondmst[xx++]=best2;
}
flag2=true;
break;
}
}
}
}
return best2;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t,n,m,x,y,z,k=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
if(x>y)swap(x,y);
edge get;
get.u=x;
get.v=y;
get.w=z;
v.push_back(get);
}
int ans=mst(n);
int ans2=secondBestMst(n);
if(n==1)flag1=true;
// cout<<ans<<" "<<ans2<<endl;
if(flag1&&!flag2)
printf("Case #%d : No second way\n",++k);
else if(!flag1)
printf("Case #%d : No way\n",++k);
else
{
sort(secondmst,secondmst+xx);
printf("Case #%d : %d\n",++k,secondmst[0]);
}
flag1=false,flag2=false;
memset(secondmst,0,sizeof(secondmst));
xx=0;
v.clear();
edges.clear();
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgUEkgYWNvcygtMSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBNWCAxMDAwMQppbnQgcGFyZW50W01YXTsKc3RydWN0IGVkZ2UKewogICAgaW50IHU7CiAgICBpbnQgdjsKICAgIGludCB3Owp9Owp2ZWN0b3IgPCBlZGdlID4gdjsKdmVjdG9yPGludD5lZGdlczsKaW50IHNlY29uZG1zdFsyMDJdLHh4PTA7CmJvb2wgZmxhZzEsZmxhZzI7CmJvb2wgY29tcChlZGdlIHgsZWRnZSB5KQp7CiAgICBpZih4Lnc8eS53KXJldHVybiB0cnVlOwogICAgZWxzZQogICAgICAgIHJldHVybiBmYWxzZTsKfQppbnQgRmluZChpbnQgeCkKewogICAgaWYocGFyZW50W3hdPT14KXJldHVybiB4OwogICAgcGFyZW50W3hdPUZpbmQocGFyZW50W3hdKTsKICAgIHJldHVybiBwYXJlbnRbeF07Cn0KaW50IG1zdChpbnQgbikKewogICAgc29ydCh2LmJlZ2luKCksdi5lbmQoKSxjb21wKTsKICAgIGZvcihpbnQgaT0xOyBpPD1uOyBpKyspcGFyZW50W2ldPWk7CiAgICBpbnQgYz0wLGFucz0wLGw9di5zaXplKCk7CiAgICBpZihsPT0wKWZsYWcxPXRydWU7CiAgICBmb3IoaW50IGk9MDsgaTxsOyBpKyspCiAgICB7CgogICAgICAgIGludCBwPUZpbmQodltpXS51KTsKICAgICAgICBpbnQgcT1GaW5kKHZbaV0udik7CgogICAgICAgIGlmKHAhPXEpCiAgICAgICAgewoKCiAgICAgICAgICAgIGVkZ2VzLnB1c2hfYmFjayhpKTsKCgogICAgICAgICAgICBwYXJlbnRbcF09cTsKCiAgICAgICAgICAgICsrYzsKICAgICAgICAgICAgYW5zICs9IHZbaV0udzsKCiAgICAgICAgICAgIGlmKGM9PW4tMSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZmxhZzE9dHJ1ZTsKICAgICAgICAgICAgICAgIGJyZWFrOwoKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gYW5zOwp9CmludCBzZWNvbmRCZXN0TXN0KGludCBuKQp7CiAgICBpbnQgYmVzdDI9SU5UX01BWCxjPTA7CiAgICBpbnQgbGVuPWVkZ2VzLnNpemUoKTsKICAgIGZvcihpbnQgaz0wOyBrPGxlbjsgaysrKQogICAgewogICAgICAgIGZvcihpbnQgaT0xOyBpPD1uOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBwYXJlbnRbaV09aTsKICAgICAgICB9CiAgICAgICAgaW50IHM9MDsKICAgICAgICBjPTA7CiAgICAgICAgZm9yKGludCBpPTA7IGk8di5zaXplKCk7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKGVkZ2VzW2tdPT1pKWNvbnRpbnVlOwogICAgICAgICAgICBpbnQgcD1GaW5kKHZbaV0udSk7CiAgICAgICAgICAgIGludCBxPUZpbmQodltpXS52KTsKICAgICAgICAgICAgaWYocCE9cSkKICAgICAgICAgICAgewoKICAgICAgICAgICAgICAgIHBhcmVudFtwXT1xOwogICAgICAgICAgICAgICAgYysrOwogICAgICAgICAgICAgICAgcyArPSB2W2ldLnc7CiAgICAgICAgICAgICAgICBpZihjPT1uLTEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYoYmVzdDI+cykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGJlc3QyPXM7CiAgICAgICAgICAgICAgICAgICAgICAgIHNlY29uZG1zdFt4eCsrXT1iZXN0MjsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZmxhZzI9dHJ1ZTsKICAgICAgICAgICAgICAgICAgICBicmVhazsKCiAgICAgICAgICAgICAgICB9CgoKCiAgICAgICAgICAgIH0KCiAgICAgICAgfQoKICAgIH0KCiAgICByZXR1cm4gYmVzdDI7Cn0KaW50IG1haW4oKQp7CgogICAgLy8gZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgLy8gZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiAgICBpbnQgdCxuLG0seCx5LHosaz0wOwogICAgc2NhbmYoIiVkIiwmdCk7CgogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIHNjYW5mKCIlZCVkIiwmbiwmbSk7CiAgICAgICAgZm9yKGludCBpPTE7IGk8PW07IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCVkJWQiLCZ4LCZ5LCZ6KTsKICAgICAgICAgICAgaWYoeD55KXN3YXAoeCx5KTsKICAgICAgICAgICAgZWRnZSBnZXQ7CiAgICAgICAgICAgIGdldC51PXg7CiAgICAgICAgICAgIGdldC52PXk7CiAgICAgICAgICAgIGdldC53PXo7CiAgICAgICAgICAgIHYucHVzaF9iYWNrKGdldCk7CgogICAgICAgIH0KCgoKCgogICAgICAgIGludCBhbnM9bXN0KG4pOwogICAgICAgIGludCBhbnMyPXNlY29uZEJlc3RNc3Qobik7CgogICAgICAgIGlmKG49PTEpZmxhZzE9dHJ1ZTsKICAgICAgICAvLyBjb3V0PDxhbnM8PCIgICAiPDxhbnMyPDxlbmRsOwogICAgICAgIGlmKGZsYWcxJiYhZmxhZzIpCiAgICAgICAgICAgIHByaW50ZigiQ2FzZSAjJWQgOiBObyBzZWNvbmQgd2F5XG4iLCsrayk7CiAgICAgICAgZWxzZSBpZighZmxhZzEpCiAgICAgICAgICAgIHByaW50ZigiQ2FzZSAjJWQgOiBObyB3YXlcbiIsKytrKTsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBzb3J0KHNlY29uZG1zdCxzZWNvbmRtc3QreHgpOwogICAgICAgICAgICBwcmludGYoIkNhc2UgIyVkIDogJWRcbiIsKytrLHNlY29uZG1zdFswXSk7CgoKICAgICAgICB9CgogICAgICAgIGZsYWcxPWZhbHNlLGZsYWcyPWZhbHNlOwogICAgICAgIG1lbXNldChzZWNvbmRtc3QsMCxzaXplb2Yoc2Vjb25kbXN0KSk7CiAgICAgICAgeHg9MDsKICAgICAgICB2LmNsZWFyKCk7CiAgICAgICAgZWRnZXMuY2xlYXIoKTsKCgoKICAgIH0KCgoKICAgIHJldHVybiAwOwp9Cg==