#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<queue>
#include<deque>
#include<climits>
#include<numeric>
#include<cassert>
#include<functional>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define fi(i,j,k) fill(i[0],i[0]+j*j,k)
#define INF 1<<27
#define F first
#define S second
static const double eps=1e-10;
typedef long long ll;
using namespace std;
typedef pair<int,int> P;
int h,w;
char cmap[110][110];
P pos[110];
int index,matrix[110][110];
int imap[110][110];
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {1,0,-1,0};
static const int dx8[8] = {0,1,1,1,0,-1,-1,-1};
static const int dy8[8] = {-1,-1,0,1,1,1,0,-1};
static const int dx16[16] = {0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1};
static const int dy16[16] = {-2,-2,-2,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2};

int D[110][110];
bool used[110][110];

void bfs(P s,P g){
  rep(i,h)rep(j,w){
    D[i][j] = INF;
    used[i][j] = false;
  }
  queue<P> que;
  que.push(s);
  D[s.S][s.F] = 0;
  used[s.S][s.F] = true;

  while(!que.empty()){
    P p = que.front(); que.pop();
    //if(p == g)return D[g.S][g.F];

    for(int i=0;i<4;i++){
      int nx = p.F+dx[i],ny = p.S+dy[i];
      if(0<= nx && nx < w && 0<= ny && ny < h && cmap[ny][nx] != '#' && /*!used[ny][nx]*/ D[ny][nx] > D[p.S][p.F] +imap[p.S][p.F]){
	D[ny][nx] = min(D[p.S][p.F] + imap[p.S][p.F],D[ny][nx]);
	//cout << "nx = " << nx << ", ny = " << ny << ", D[ny][nx] =" << D[ny][nx] << endl;  
	//used[ny][nx] = true;
	que.push(P(nx,ny));
      }
    }
  }
  //return INF;
}


void display(){
  for(int i=0;i<h;i++)
    {
      rep(j,w){
	cout << cmap[i][j] << " ";
      }
      cout<< endl;
    }
  cout << endl;
  for(int i=0;i<h;i++)
    {
      rep(j,w){
	cout << imap[i][j] << " ";
      }
      cout<< endl;
    }
  cout << endl;

  rep(i,index){
    rep(j,index){
      cout << matrix[i][j] << " ";
    }
    cout<< endl;
  }
  cout << endl;

}

int main(){
  while(cin >> w >> h){
  int sindex,lim = 1;
  index = 1;
  
  rep(i,h)rep(j,w)imap[i][j] = 1;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> cmap[i][j];
      matrix[i][j] = INF;
      if(cmap[i][j] == 'S'){
	pos[0] = P(j,i);
      }
      else if(cmap[i][j] == 'M')lim++;
      else if(cmap[i][j] == 'G'){
	lim++;
      }
    }
  }
 
  rep(i,h){
    rep(j,w){
      
      if(cmap[i][j] == 'G'){
	 pos[lim-1] = P(j,i);
      }
       else if(cmap[i][j] == 'M'){
	 assert(index != lim-1);
	pos[index++] = P(j,i);
      }
      else if(cmap[i][j] == '#'){
	for(int k=0;k<8;k++){
	  
	  int nx = j+dx8[k],ny = i+dy8[k];
	  if(0<=nx && nx<w && 0<=ny && ny <h && cmap[ny][nx] != '#'){
	    imap[ny][nx] = 3;
	  }
	}
	for(int k=0;k<16;k++){
	  int nx = j+dx16[k],ny = i+dy16[k];
	  if(0<=nx && nx<w && 0<=ny && ny <h && cmap[ny][nx] != '#'){
	    imap[ny][nx] = max(imap[ny][nx],2);
	  }
	}
      }
    }
  }

  

  //rep(i,h)rep(j,w)if(cmap[i][j] == 'G')imap[i][j] = 0;
  

  index = lim;

  for(int i=0;i<index;i++){
    rep(j,index){
    
      if(i == j){
	matrix[i][j] = 0;
	continue;
      }
bfs(pos[i],pos[j]);
 matrix[i][j] = D[pos[j].S][pos[j].F];
    }
  }

  //index--;

  //display();
  int per[110];
  rep(i,index-1)per[i] = i+1;

  int sum;
  int ans=INF;
  do{
    sum=0;
    sum+=matrix[0][per[0]];

    int posi=-1;     
    for(int i=1;i<index-1;i++){
      if(i == index-2)posi = per[i];
      sum+=matrix[per[i-1]][per[i]];
    }
    //assert(posi !=-1);
    //if(posi != index-1){
    //cout <<"posi = " << posi << ",index = " << index-1 << ",presum = " << sum << ", matrix[posi][lim-1] = " << matrix[posi][lim-1] << endl;
    if(posi != -1 && posi != lim-1)sum += matrix[posi][lim-1];
    //}
    ans=min(ans,sum);
  }while(next_permutation(per,per+(index-1)));
 

  cout << ans << endl;

}
  return 0;
}

Measured memory_bytes: 1388