Untitled

#include <iostream>
#define N 101
#define oo 2000000
using namespace std;
int ans;
int m,d;
int doigiay(int u, int v)
{
	return u*60+v;
}
int min(int u, int v)
{
	if(u>v)return v;
	return u;
}
int tim[N],en[N];
int f[N][10000];
void doc()
{
	cin>>m>>d;
	int u,v;
	for(int i=0;i<=d;i++)
		for(int j=0;j<=m;j++)f[i][j]=oo;
	
	for(int i=1;i<=5;i++)
	{
		cin>>u>>v>>en[i];
		tim[i]=doigiay(u,v);
		f[1][en[i]]=min(f[1][en[i]],tim[i]);
	
	}

	for(int i=1;i<=d;i++)
		for(int j=1;j<=m;j++)if(f[i][j]!=oo)
		{
			
			for(int ii=1;ii<=5;ii++)
			{
				if(j+en[ii]<=m)
					{
						f[i+1][j+en[ii]]=min(f[i+1][j+en[ii]],f[i][j]+tim[ii]);
						//if(time[ii]==20&&j%17==0)cout<<i+1<<" "<<j+en[ii]<<" "<<f[i+1][j+en[ii]]<<"\n";
				}
			}
		}
	 ans=oo;
	 int nl;
	for(int i=1;i<=m;i++)
		{
			ans=min(ans,f[d][i]);
			
	}
	

}


int main()
{
	freopen("input.txt","r",stdin);
	int TC;
	
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		cout<<"Case #"<<tc<<"\n";
		if(ans==oo)cout<<-1<<"\n";else
		{
			cout<<ans/60<<" "<<ans%60<<"\n";
		}
		//cout<<ans<<"\n";
	}
	return 0;
}