Untitled

#include <iostream>
using namespace std;

const int MAXN = 45;

int m, n, a[6][3], edge[MAXN][MAXN][6][3], d[MAXN][3];
bool mark[MAXN];

void solve(){
	cin >> m >> n;
	for(int i = 1; i <= 5; ++i){
		cin >> a[i][1] >> a[i][2] >> a[i][3];
	}
	for(int i = 0; i <= n - 1; ++i){
		int u = i, v = i + 1;
		for(int j = 1; j <= 5; ++j){
			edge[u][v][j][1] = a[j][1] * 60 + a[j][2];
			edge[u][v][j][2] = a[j][3];
		}
	}
	for(int i = 0; i <= n; ++i){
		d[i][1] = 1e9;
		mark[i] = false;
	}
	d[0][1] = 0;
	d[0][2] = 0;
	for(int i = 0; i <= n - 1; ++i){
		int u = -1;
		for(int j = 0; j <= n; ++j){
			if(mark[j] == false){
				if(u == -1){
					u = j;
					continue;
				}
				if(d[u][1] > d[j][1]){
					u = j;
				}
			}
		}
		if(u == -1) break;
		mark[u] = true;
		int v = u + 1;
		if(v <= n && mark[v] == false){
			for(int j = 1; j <= 5; ++j){
				if(d[v][1] == d[u][1] + edge[u][v][j][1]){
					if(d[v][2] > d[u][2] + edge[u][v][j][2] && d[u][2] + edge[u][v][j][2] <= m){
						d[v][2] = d[u][2] + edge[u][v][j][2];
					}
				}
				if(d[v][1] > d[u][1] + edge[u][v][j][1] && d[u][2] + edge[u][v][j][2] <= m){
					d[v][1] = d[u][1] + edge[u][v][j][1];
					d[v][2] = d[u][2] + edge[u][v][j][2];
				}
			}
		}
	}
	if(d[n][1] == 1e9) cout << -1 << '\n';
	else{
		cout << d[n][1] / 60 << ' ' << d[n][1] % 60 << '\n';
	}
}

int main() {
	int testcase; cin >> testcase;
	for(int t = 1; t <= testcase; ++t){
		cout << "Case #" << t << '\n';
		solve();
	}
	return 0;
}