#include <stdio.h>

#include <iostream>

#include <string.h>

#include <queue>

#include <stdlib.h>

using namespace std;

const int N=;

char Map[N][N];

int a[N][N][],vis[N][N][];

int dir[][] = {{,-},{,},{-,},{,}};

int n,m,sx,sy,ex,ey;

struct node

{

    int x,y,hp,state;

    friend bool operator < (node a,node b)

    {

        return b.hp < a.hp;//在这跪了n遍。。要想优先队列里的值从小到大排列，则比较函数应该从大到小排

    }

};

bool in(int x,int y)

{

    if (x >= &&x <= n&&y >= &&y <= m)

        return true;

    return false;

}

bool judge(int x1,int y1,int x2,int y2,int c)

{

    if(abs(x1-x2)+abs(y1-y2) <= c)

        return true;

    return false;

}

void deal(int x,int y,char ch)

{

    if (ch=='A')

    {

        for (int i = x-; i <= x+; i++)

        {

            for (int j = y-; j <= y+; j++)

            {

                if(in(i,j)&&judge(x,y,i,j,))

                    a[i][j][] = ;

            }

        }

    }

    else if (ch=='B')

    {

        for (int i = x-; i <= x+; i++)

        {

            for (int j = y-; j <= y+; j++)

            {

                if (in(i,j)&&judge(x,y,i,j,))

                    a[i][j][] = ;

            }

        }

    }

    else if (ch=='C')

        a[x][y][] = ;

    else if (ch=='D')

    {

        for (int i = x-; i <= x+; i++)

        {

            for (int j = y-; j <= y+; j++)

            {

                if (in(i,j)&&judge(x,y,i,j,))

                    a[i][j][] = ;

            }

        }

    }

    else if (ch=='E')

    {

        for (int i = x-; i <= x+; i ++)

        {

            for (int j = y-; j <= y+; j ++)

            {

                if (in(i,j)&&judge(x,y,i,j,))

                    a[i][j][] = ;

            }

        }

    }

}

int bfs()

{

    priority_queue<node>q;

    while(!q.empty()) q.pop();

    q.push((struct node)

    {

        sx,sy,,

    });

    vis[sx][sy][] = ;

    while(!q.empty())

    {

        node temp,t = q.top();

        q.pop();

        printf("%d %d %d\n",t.x,t.y,t.hp);

        if (t.x==ex&&t.y==ey)

            return t.hp;

        for (int i = ; i < ; i++)

        {

            temp.x = t.x+dir[i][];

            temp.y = t.y+dir[i][];

            temp.hp = t.hp;

            temp.state = t.state;

            if (in(temp.x,temp.y)&&(Map[temp.x][temp.y]=='C'||Map[temp.x][temp.y]=='$'||Map[temp.x][temp.y]=='.'||Map[temp.x][temp.y]=='!'))

            {

                for (int k = ; k < ; k++)

                {

                    if((temp.state&(<<k))==&&a[temp.x][temp.y][k])

                    {

                        temp.hp+=a[temp.x][temp.y][k];

                        temp.state+=(<<k);

                    }

                }

                if (!vis[temp.x][temp.y][temp.state])

                {

                    vis[temp.x][temp.y][temp.state] = ;

                    q.push(temp);

                }

            }

        }

    }

    return -;

}

int main()

{

    int t,o = ;

    cin>>t;

    while((t--))

    {

        o++;

        cin>>n>>m;

        memset(a,,sizeof(a));

        memset(vis,,sizeof(vis));

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

        {

            for (int j = ; j <= m; j++)

            {

                cin>>Map[i][j];

                if (Map[i][j]=='A'||Map[i][j]=='B'||Map[i][j]=='C'||Map[i][j]=='D'||Map[i][j]=='E')

                    deal(i,j,Map[i][j]);

                if (Map[i][j]=='$')

                {

                    sx = i;

                    sy = j;

                }

                if (Map[i][j]=='!')

                {

                    ex = i;

                    ey = j;

                }

            }

        }

        int ans = bfs();

        printf("Case %d: %d\n",o,ans);

    }

    return ;

}