#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
#include <iostream>
using namespace std;

const int INF = 1 << 28;
int H, W;
int sx, sy, gx, gy;
int board[110][110], dist[10][10], dp[1 << 10][10], rec[110][110];

int nxt[] = {0, 1, 1, 2, 3};
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int ex[] = {0, 0, 1, -1};
int ey[] = {1, -1, 0, 0};

void get_board(deque< pair<int, int> > holes) {
  int N = holes.size();

  for(int i=0; i<N; i++) {
    int ix = holes[i].first, iy = holes[i].second;
    queue< pair<int, int> > que;
    que.push(make_pair(ix, iy));

    while(que.size()) {
      int cx, cy; tie(cx, cy) = que.front(); que.pop();
      for(int k=0; k<8; k++) {
        int nx = cx + dx[k], ny = cy + dy[k];
        if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if(board[nx][ny] == 4) continue;

        int cst = nxt[ board[cx][cy] ];
        if(cst > board[nx][ny]) {
          board[nx][ny] = cst;
          que.push(make_pair(nx, ny));
        }
      }
    }
  }
}

struct Elem {
  int x, y, cost;
  bool operator<(const Elem &e) const {
    return cost > e.cost;
  }
};

void bfs(deque< pair<int, int> > treasures, int id) {
  fill(rec[0], rec[110], INF);

  int ix, iy; tie(ix, iy) = treasures[id];
  priority_queue<Elem> que;
  rec[ix][iy] = 0;
  que.push(Elem{ix, iy, 0});

  while(que.size()) {
    Elem cur = que.top(); que.pop();
    int x = cur.x, y = cur.y, cst = cur.cost;

    for(int k=0; k<4; k++) {
      int nx = x + ex[k], ny = y + ey[k];
      if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
      if(board[nx][ny] == INF) continue;

      int n_cost = cst + max(1, board[x][y]);
      if(rec[nx][ny] > n_cost) {
        rec[nx][ny] = n_cost;
        que.push(Elem{nx, ny, n_cost});
      }
    }
  }

  int N = treasures.size();
  for(int i=0; i<N; i++) {
    int tx, ty; tie(tx, ty) = treasures[i];
    // printf("tx = %d, ty = %d, cost = %d\n", tx, ty, rec[tx][ty]);
    dist[id][i] = rec[tx][ty];
  }
}

int main() {
  cin >> W >> H;

  deque< pair<int, int> > holes, treasures;
  for(int i=0; i<H; i++) {
    for(int j=0; j<W; j++) {
      char c; cin >> c;
      if(c == 'S') {
        sx = i, sy = j;
      }
      else if(c == 'G') {
        gx = i, gy = j;
      }
      else if(c == '#') {
        holes.push_back(make_pair(i, j));
        board[i][j] = 4;
      }
      else if(c == 'M') {
        treasures.push_back(make_pair(i, j));
      }
    }
  }

  get_board(holes);
  for(int i=0; i<holes.size(); i++) {
    int x, y; tie(x, y) = holes[i];
    board[x][y] = INF;
  }


  /*
  // debug
  for(int i=0; i<H; i++) {
    for(int j=0; j<W; j++) {
      cout << board[i][j];
    }
    cout << endl;
  }
  */
  
  
  int N = treasures.size();
  int si = 0, gi = N + 1;
  treasures.push_front(make_pair(sx, sy));
  treasures.push_back (make_pair(gx, gy));
  N += 2;
  
  for(int i=0; i<N; i++) {
    bfs(treasures, i);
  }

  /*
  // debug
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      cout << dist[i][j] << " ";
    }
    cout << endl;
  }
  */

  int fullbit = (1<<N) - 1;

  fill(dp[0], dp[1 << 10], INF);
  dp[1][0] = 0;
  for(int bit=0; bit<(1<<N); bit++) {
    for(int i=0; i<N; i++) {
      for(int k=0; k<N; k++) {
        if(!(bit >> i & 1)) continue;
        if(bit >> k & 1) continue;
        int nbit = bit | (1 << k);
        // if(k == N-1 && nbit != fullbit) continue;

        int cost = dist[i][k];
        dp[nbit][k] = min(dp[nbit][k], dp[bit][i] + cost);
      }
    }
  }

  int ans = dp[fullbit][N-1];
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3296