#include<iostream>
#include<cstring>
#include<vector>
#define maxx 0x3f3f3f3f
using namespace std;
int c,n,m,s,w,t;
struct crossing{
	int s,w,t;
}cr[25][25];
struct point{
	int x,y,w;
};
int dis[45][45];
bool vis[45][45];
vector<point> p[45][45];
void build(){
	for(int i=0;i<2*n;i++){
		for(int j=1;j<2*m;j+=2){
			p[i][j].push_back({i,j+1,2});
			p[i][j+1].push_back({i,j,2});
		}
		for(int j=0;j<2*m;j+=2){
			p[i][j].push_back({i,j+1,-1});
			p[i][j+1].push_back({i,j,-1});
		}
	}
	for(int j=0;j<2*m;j++){
		for(int i=0;i<2*n;i+=2){
			p[i][j].push_back({i+1,j,-1});
			p[i+1][j].push_back({i,j,-1});
		}
		for(int i=1;i<2*n;i+=2){
			p[i][j].push_back({i+1,j,2});
			p[i+1][j].push_back({i,j,2});
		}
	}
}
void update(int x1,int y1,int x2,int y2,int &weight){
	int s=cr[x1/2][y1/2].s,w=cr[x1/2][y1/2].w;
	int neww=0;
	if(dis[x1][y1]>=cr[x1/2][y1/2].t){
		neww=(dis[x1][y1]-cr[x1/2][y1/2].t)%(s+w);
	}
	else{
		//neww=(cr[x1/2][y1/2].t-dis[x1][y1])%(s+w);
		neww=((s+w)-(cr[x1/2][y1/2].t-dis[x1][y1])%(s+w))%(s+w);
	}
	if(x1==x2){
		if(neww>=s){
			weight=1;
			return;
		}
		else{
			weight=s-neww+1;
			return;
		}
	}
	if(y1==y2){
		if(neww>=s){
			weight=w-neww+s+1;
			return;
		}
		else{
			weight=1;
			return;
		}
	}
}
void dj(){
	for(int i=0;i<2*n;i++){
		for(int j=0;j<2*m;j++){
			int q=0,w=0,mind=maxx;
    		for(int k=0;k<2*n;k++){
    			for(int l=0;l<2*m;l++){
    				if(!vis[k][l]&&dis[k][l]<mind){
    					q=k,w=l;
						mind=dis[k][l];
					} 
				}
			}	
    		vis[q][w]=true;
    		//for(auto ed:p[q][w]){
    		for(int o=0;o<p[q][w].size();o++){
    			/*if(ed.w==-1){
    				update(q,w,ed.x,ed.y,ed.w);
				}
    			if(dis[ed.x][ed.y]>dis[q][w]+ed.w){
    				dis[ed.x][ed0.y]=dis[q][w]+ed.w;	
				}*/
				if(p[q][w][o].w==-1){
					update(q,w,p[q][w][o].x,p[q][w][o].y,p[q][w][o].w);
				}
				if(dis[p[q][w][o].x][p[q][w][o].y]>dis[q][w]+p[q][w][o].w){
					dis[p[q][w][o].x][p[q][w][o].y]=dis[q][w]+p[q][w][o].w;
				}
    		}
  		}
	}
}
int main(){
	cin>>c;
	for(int u=1;u<=c;u++){
		for(int i=0;i<2*n;i++){
			for(int j=0;j<2*m;j++){
				p[i][j].clear();
			}
		}
		memset(cr,0,sizeof(cr));
		memset(dis,maxx,sizeof(dis));
		memset(vis,0,sizeof(vis));
		cin>>n>>m;
		build();
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>s>>w>>t;
				cr[i][j]={s,w,t};
			}
		}
		//vis[0][0]=1;
		dis[0][0]=0;
		dj();
//		for(int i=0;i<2*n;i++){
//			for(int j=0;j<2*m;j++){
//				cout<<dis[i][j]<<" ";
//			}
//			cout<<endl;
//		}
		cout<<"Case #"<<u<<": ";
		cout<<dis[2*n-1][2*m-1];
		putchar('\n');
	}
	return 0;
}

用的是dijkstra+动态更改权值跑最短路，具体看代码