import java.io.*;
import java.util.*;

public class MazeSolver {
    static class P implements Comparable<P> {
        public int r, c;
        public int dist;
        public P prev;
        public P(int row, int col) {
            r = row;
            c = col;
            dist = 0;
            prev = null;
        }
        public P extend(int row, int col, int dist) {
            P ret = new P(row, col);
            ret.dist = this.dist + dist;
            ret.prev = this;
            return ret;
        }
        public int compareTo(P other) {
            // if this < other, return negative
            // if this == other, return 0
            // if this > other, return positive
            return Integer.compare(this.dist, other.dist);
        }
        public boolean equals(Object other1) {
            P other = (P) other1;
            return this.row == other.row && this.col == other.col;
        }
        public int hashCode() {
            return this.row * 137 + this.col;
        }
    }
    public static void main(String[] argv) throws IOException {
        Scanner sc = new Scanner(new File("data.dat"));
        int rows = sc.nextInt(), cols = sc.nextInt(); sc.nextLine();
        char[][] grid = new char[rows][];
        P start = null, end = null;
        for (int i = 0; i < rows; i++) {
            grid[i] = sc.nextLine().toCharArray();
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '@') {
                    start = new P(i, j);
                }
                if (grid[i][j] == '$') {
                    end = new P(i, j);
                }
            }
        }
        HashSet<P> visited = new HashSet<>();
        PriorityQueue<P> Q = new PriorityQueue<>();
        Q.add(start);
        while (!Q.isEmpty()) {
            P cur = Q.remove();
            if (visited.contains(cur)) continue;
            visited.add(cur);
            if (cur.equals(end)) {
                end = cur;
                break;
            }
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    // both r and c in [-1, 1]
                    if (Math.abs(dr) == Math.abs(dc)) {
                        continue;
                    }
                    int nr = cur.r + dr, nc = cur.c + dc;
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    int dist = 1;
                    if (grid[nr][nc] == '#') continue;
                    if (grid[nr][nc] == '^') dist = 5;
                    Q.add(cur.extend(cur.r + dr, cur.c + dc), dist);
                }
            }
        }
        // end contains the whole chain and total distance
        // example: if you want in order
        ArrayList<P> path = new ArrayList<P>();
        P cur = end;
        while (cur != null) {
            path.add(cur); // added backwards
            cur = cur.prev;
        }
        Collections.reverse(path);
        // if you don't care, instead of adding to arraylist, work with it
    }
}