#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <cstring>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(int)n;i++)

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > pti;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};

const double EPS = 1e-9;

#define InRange(y,x) (0<=(y) and (y)<H and 0<=(x) and (x)<W)

const int INF = 1 << 30;

int main(){
    int W,H;
    cin >> W >> H;
    vector<string> field(H);
    for(int i=0;i<H;i++){
        cin >> field[i];
    }
    vector<vector<int> > goout(H,vector<int>(W,1));
    pair<int,int> S,G;
    vector<pair<int,int> > M;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(field[i][j] == '#'){
                for(int k=-2;k<=2;k++){
                    for(int l=-2;l<=2;l++){
                        if(InRange(i+k,j+l)){
                            int maxi = max(abs(k),abs(l));
                            if(maxi == 0){
                                goout[i+k][j+l] = max(goout[i+k][j+l],INF);
                            }else if(maxi == 1){
                                goout[i+k][j+l] = max(goout[i+k][j+l],3);
                            }else{
                                goout[i+k][j+l] = max(goout[i+k][j+l],2);
                            }
                        }
                    }
                }
            }else if(field[i][j] == 'S'){
                S = make_pair(i,j);
            }else if(field[i][j] == 'G'){
                G = make_pair(i,j);
            }else if(field[i][j] == 'M'){
                M.push_back(make_pair(i,j));
            }
        }
    }

    M.push_back(S);
    M.push_back(G);

    int makimono = M.size()-2;
    vector<vector<int> > mdist(M.size(),vector<int>(M.size()));
    for(int i=0;i<M.size();i++){
        vector<vector<int> > dist(H,vector<int>(W));
        vector<vector<char> > used(H,vector<char>(W,false));
        priority_queue<pti,vector<pti>,greater<pti> > que;
        que.push(make_pair(0,M[i]));
        while(not que.empty()){
            int cnt = que.top().first;
            int y = que.top().second.first;
            int x = que.top().second.second;
            que.pop();
            if(used[y][x]) continue;
            dist[y][x] = cnt;
            used[y][x] = true;
            for(int j=0;j<4;j++){
                int ny = y + dy[j];
                int nx = x + dx[j];
                if(InRange(ny,nx)){
                    que.push(make_pair(cnt+goout[y][x],make_pair(ny,nx)));
                }
            }
        }
        for(int j=0;j<M.size();j++){
            int y = M[j].first;
            int x = M[j].second;
            mdist[i][j] = dist[y][x];
        }
    }
    int dp[1 << makimono][makimono];
    for(int i=0;i<(1 << makimono);i++){
        for(int j=0;j<makimono;j++){
            dp[i][j] = INF;
        }
    }
    for(int i=0;i<makimono;i++){
        dp[1<<i][i] = mdist[makimono][i];
    }
    for(int i=0;i<(1<<makimono);i++){
        for(int j=0;j<makimono;j++){
            if(dp[i][j] == INF) continue;
            for(int k=0;k<makimono;k++){
                if(i & (1 << k)) continue;
                dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j]+mdist[j][k]);
            }
        }
    }
    int ret = INF;
    for(int i=0;i<makimono;i++){
        ret = min(ret,dp[(1<<makimono)-1][i]+mdist[i][makimono+1]);
    }
    cout << ret << endl;
    //M.pop_back();
    //M.pop_back();
    return 0;
}

Measured memory_bytes: 1488