#include <iostream>
#include <numeric>
#include <queue>
#include <cstring>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef long long ll;
typedef vector<ll> vll;
const int inf=10000000;
int H,W,startx,starty,goalx,goaly;
string board[105];
int cost[105][105];
int d[105][105];
bool visited[150][105];
int dx8[]={-1,-1,0,1,1,1,0,-1};
int dy8[]={0,1,1,1,0,-1,-1,-1};
int dy[]={0,1,0,-1};
int dx[]={-1,0,1,0};

typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;

void costset(int sx,int sy,int times)
{
  if(times==2) return;
  int nowx=sx;
  int nowy=sy;
  int cos=3-times;
  for(int k=0;k<8;k++)
    {
      int nx=nowx+dx8[k];
      int ny=nowy+dy8[k];
      if(nx<0 || W<=nx || ny<0 || H<=ny) continue;
      cost[ny][nx]=max(cost[ny][nx],cos);
      costset(nx,ny,times+1);
    }
}

int solve(int sx,int sy,int gx,int gy)
{
  for(int i=0;i<H;i++)
    {
      for(int j=0;j<W;j++)
	{
	  d[i][j]=inf;
	}
    }
  d[sy][sx]=0;
  priority_queue<PP,vector<PP> ,greater<PP>> p;
  p.push(PP(0,P(sy,sx)));
  int nowy,nowx;
  while(!p.empty())
    {
      PP now=p.top();p.pop();
      nowy=now.second.first;
      nowx=now.second.second;
      if(nowx==gx && nowy==gy) break;
      for(int k=0;k<4;k++)
	{
	  int ny=nowy+dy[k];
	  int nx=nowx+dx[k];
	  if(ny<0 || H<=ny || nx<0 || W<=nx || board[ny][nx]=='#') continue;
	  if(d[nowy][nowx]+cost[nowy][nowx]>=d[ny][nx]) continue;
	  if(d[ny][nx]==inf || d[ny][nx]>d[nowy][nowx]+cost[nowy][nowx])
	    {
	      d[ny][nx]=d[nowy][nowx]+cost[nowy][nowx];
	      p.push(PP(d[ny][nx],P(ny,nx)));
	    }
	}
    }
  return d[gy][gx];
}

int main(int argc,char const* argv[])
{
  int ans=20000000;
  int scroll=0;
  int pat=1;
  int graph[10][10];
  for(int i=0;i<10;i++)
    {
      for(int j=0;j<10;j++)
	{
	  graph[i][j]=inf;
	}
    }
  vector<P> route;
  cin >> W >> H;
  for(int i=0;i<H;i++)
    {
      cin >> board[i];
    }
  for(int i=0;i<H;i++)
    {
      for(int j=0;j<W;j++)
	{
	  cost[i][j]=1;
	  if(board[i][j]=='M') route.push_back(P(i,j));
	  if(board[i][j]=='G') {goaly=i;goalx=j;}
	  if(board[i][j]=='S') {starty=i;startx=j;}
	}
    }
  sort(route.begin(),route.end());
  for(int i=0;i<H;i++)
    {
      for(int j=0;j<W;j++)
	{
	  if(board[i][j]=='#')
	    {
	      costset(j,i,0);
	    }
	  if(board[i][j]=='M')
	    {
	      scroll++;
	    }
	}
    }
  for(int i=0;i<route.size();i++)
    {
      graph[0][i+1]=solve(startx,starty,route[i].second,route[i].first);
      graph[i+1][6]=solve(route[i].second,route[i].first,goalx,goaly);					      
      for(int j=0;j<route.size();j++)
	{
	  if(i==j) continue;
	  int stx=route[i].second;
	  int sty=route[i].first;
	  int gox=route[j].second;
	  int goy=route[j].first;
	  graph[i+1][j+1]=solve(stx,sty,gox,goy);
	  //graph[j+1][i+1]=graph[i+1][j+1];
	}
    }
   vector<int> walk(scroll);
   iota(walk.begin(),walk.end(),1);
   do
     {
       int tmp=0;
       int prev=0;
       int to=0;
       for(auto x:walk) 
	 {
	   to=x;
	   tmp+=graph[prev][to];
	   prev=x;
	 }
       tmp+=graph[to][6];
       ans=min(ans,tmp);
     } while(next_permutation(walk.begin(),walk.end()));
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3280