#include<cstdio>

#include<algorithm>

using namespace std;

#define N 100010

struct Edge{

	int u,v,w;

}edges[N];

bool cmp(const Edge &a,const Edge &b){

	return a.w<b.w;

}

bool cm2(const Edge &a,const Edge &b){

	return a.w>b.w;

}

int T,n,m,a[1010],mm;

int fa[N];

int findroot(int x){

	return x==fa[x] ? x : fa[x]=findroot(fa[x]);

}

int kruscal(){

	for(int i=1;i<=n;++i){

		fa[i]=i;

	}

	int tot=0,sum=0;

	for(int i=1;i<=m;++i){

		int f1=findroot(edges[i].u),f2=findroot(edges[i].v);

		if(f1!=f2){

			fa[f1]=f2;

			++tot;

			sum+=edges[i].w;

			if(tot==n-1){

				return sum;

			}

		}

	}

	return -1;

}

int main(){

//	freopen("f.in","r",stdin);

	scanf("%d",&T);

	a[1]=1; a[2]=2;

	for(int i=3;;++i){

		a[i]=a[i-1]+a[i-2];

		if(a[i]>100000){

			mm=i-1;

			break;

		}

	}

	for(int zu=1;zu<=T;++zu){

		scanf("%d%d",&n,&m);

		for(int i=1;i<=m;++i){

			scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);

		}

		sort(edges+1,edges+m+1,cmp);

		int minn=kruscal();

		sort(edges+1,edges+m+1,cm2);

		int maxx=kruscal();

		if(minn==-1 || maxx==-1){

			printf("Case #%d: No\n",zu);

			continue;

		}

		bool flag=0;

		for(int i=1;i<=mm;++i){

			if(a[i]>=minn && a[i]<=maxx){

				flag=1;

				printf("Case #%d: Yes\n",zu);

				break;

			}

		}

		if(!flag){

			printf("Case #%d: No\n",zu);

		}

	}

	return 0;

}