// Slower C++ solution:
#include<iostream>

#include<string>

#include<algorithm>

#include<queue>

#include<map>

#include<cstring>

using namespace std;

typedef pair<int,int> Pt;

typedef pair<Pt,Pt> P;

#define fr first

#define sc second

int h,w,sx,sy,gx,gy,d[]={0,1,0,-1},Time[101][101],cnt;

bool used[101][101][1<<5];

int ldx[]={-1,-1,-1,0,1,1,1,0},ldy[]={-1,0,1,1,1,0,-1,-1};

int sdx[]={-2,-2,-2,-2,-2,-1,0,1,2,2,2,2,2,1,0,-1};

int sdy[]={-2,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2};

char mas[101][101];

void BAD(int,int);

int bfs();

bool judge(int x,int y){ return ((x>=0&&x<h&&y>=0&&y<w)? true : false); }

int main(){

  cin >> w >> h;

  for(int i=0;i<h;i++) for(int j=0;j<w;j++) Time[i][j] = 1;



  for(int i=0;i<h;i++){

    for(int j=0;j<w;j++){

      cin >> mas[i][j];

      if(mas[i][j] == 'S') sx = i,sy = j;

      else if(mas[i][j] == 'G') gx = i,gy = j;

      else if(mas[i][j] == '#') BAD(i,j);

      else if(mas[i][j] == 'M') mas[i][j] = cnt++;

    }

  }

  cout << bfs() << endl;

}



int bfs(){

  memset(used,false,sizeof(used));

  priority_queue<P,vector<P>,greater<P> > que;

  que.push(P(Pt(0,sx),Pt(sy,0)));

  while(!que.empty()){

    P p = que.top();

    int t = p.fr.fr,px = p.fr.sc,py = p.sc.fr,BIT = p.sc.sc;

    que.pop();

    if(used[px][py][BIT])continue;

    used[px][py][BIT] = true;

    if(px == gx && py == gy && BIT ==(1<<cnt)-1 )return t;

    for(int i=0;i<4;i++){

      int nx = px + d[i],ny = py + d[3-i],bit = BIT;

      if(!judge(nx,ny)) continue;

      if(mas[nx][ny] == '#') continue;

      if(mas[nx][ny]>=0&&mas[nx][ny]<=10) bit |= 1<<mas[nx][ny];

      que.push(P(Pt(t+Time[px][py],nx),Pt(ny,bit)));

    }

  }

}

void BAD(int x,int y){

  for(int i=0;i<8;i++){

    int nx=x+ldx[i],ny=y+ldy[i];

    if(judge(nx,ny)) Time[nx][ny] = 3;

  }

  for(int i=0;i<16;i++){

    int nx=x+sdx[i],ny=y+sdy[i];

    if(judge(nx,ny)) Time[nx][ny] = max(Time[nx][ny],2);

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.3198723150010774x):
#include<iostream>

#include<string>

#include<algorithm>

#include<queue>

#include<map>

#include<cstring>

using namespace std;

typedef pair<int,int> Pt;

typedef pair<Pt,Pt> P;

#define fr first

#define sc second

int h,w,sx,sy,gx,gy,d[]={0,1,0,-1},Time[101][101],cnt;

bool used[101][101][1<<5];

int ldx[]={-1,-1,-1,0,1,1,1,0},ldy[]={-1,0,1,1,1,0,-1,-1};

int sdx[]={-2,-2,-2,-2,-2,-1,0,1,2,2,2,2,2,1,0,-1};

int sdy[]={-2,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2};

char mas[101][101];

void BAD(int,int);

int bfs();

bool judge(int x,int y){ return ((x>=0&&x<h&&y>=0&&y<w)? true : false); }

int main(){

  cin >> w >> h;

  for(int i=0;i<h;i++){

    for(int j=0;j<w;j++){

      cin >> mas[i][j];

      if(mas[i][j] == 'S') sx = i,sy = j;

      else if(mas[i][j] == 'G') gx = i,gy = j;

      else if(mas[i][j] == '#') BAD(i,j);

      else if(mas[i][j] == 'M') mas[i][j] = cnt++;

    }

  }

  cout << bfs() << endl;

}

 

int bfs(){

  priority_queue<P,vector<P>,greater<P> > que;

  que.push(P(Pt(0,sx),Pt(sy,0)));

  while(!que.empty()){

    P p = que.top();

    int t = p.fr.fr,px = p.fr.sc,py = p.sc.fr,BIT = p.sc.sc;

    que.pop();

    if(used[px][py][BIT])continue;

    used[px][py][BIT] = true;

    if(px == gx && py == gy && BIT ==(1<<cnt)-1 )return t;

    for(int i=0;i<4;i++){

      int nx = px + d[i],ny = py + d[3-i],bit = BIT;

      if(!judge(nx,ny)) continue;

      if(mas[nx][ny] == '#') continue;

      if(mas[nx][ny]>=0&&mas[nx][ny]<=10) bit |= 1<<mas[nx][ny];

      que.push(P(Pt(t+Time[px][py]+1,nx),Pt(ny,bit)));

    }

  }

}

void BAD(int x,int y){

  for(int i=0;i<8;i++){

    int nx=x+ldx[i],ny=y+ldy[i];

    if(judge(nx,ny)) Time[nx][ny] = 2;

  }

  for(int i=0;i<16;i++){

    int nx=x+sdx[i],ny=y+sdy[i];

    if(judge(nx,ny)) Time[nx][ny] = max(Time[nx][ny],1);

  }

}