#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000

int di[4] = {0, -1, 0, 1};
int dj[4] = {1, 0, -1, 0};

vector<int> dijk(int s, int v, vector<vector<pair<int, int> > > adjlist){
    
    priority_queue <pair<int, int> > wait;
    vector<int> result(v, INF);

    //スタート地点を追加
    result[s] = 0;
    wait.push(make_pair(0, s));

    //ダイクストラ本体
    while(!wait.empty()){    //waitが空になるまで

        int nowpoint = wait.top().second;
        int nowcost = -wait.top().first;
        wait.pop();

        if(result[nowpoint] < nowcost) continue;


        //今いる頂点と隣接しているすべての頂点をなめる
        for(int i = 0; i < adjlist[nowpoint].size(); i++){

            int nextpoint = adjlist[nowpoint][i].second;
            int nextcost = nowcost + adjlist[nowpoint][i].first;
            //現時点より安く到達できそうであれば、結果を更新して優先度付きキューに格納
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push(make_pair(-nextcost, nextpoint));
            }
        }
    }
    
    return result;         //結果列を返す
}

int main(){

    int h, w; cin >> w >> h;
    int si, sj, gi, gj;
    vector<vector<int> > gold(h + 2, vector<int> (w + 2, 0));
    vector<vector<int> > canGo(h + 2, vector<int> (w + 2, 0));

    int cnt = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            char in; cin >> in;
            if(in == '#'){
                canGo[i][j] = 4;
            }else{
                canGo[i][j] = 1;

                if(in == 'S'){
                    si = i;
                    sj = j;
                }

                if(in == 'G'){
                    gi = i;
                    gj = j;
                }

                if(in == 'M'){
                    cnt++;
                    gold[i][j] = cnt;
                }
            }
        }
    }

    int Map[110][110][(1 << 5)];

    int node = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            for(int bit = 0; bit < (1 << 5); bit++){
                Map[i][j][bit] = node;
                node++;
            }
        }
    }

    //cout << cnt << " " << node << endl;

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){

            //あなあなら
            if(canGo[i][j] == 4){
                

                for(int k = i - 2; k <= i + 2; k++){
                    for(int l = j - 2; l <= j + 2; l++){
                        if(k < 1 || h < k || l < 1 || w < l) continue;

                        canGo[k][l] = max(canGo[k][l], 2);
                    }
                }

                for(int k = i - 1; k <= i + 1; k++){
                    for(int l = j - 1; l <= j + 1; l++){
                        if(k < 1 || h < k || l < 1 || w < l) continue;

                        canGo[k][l] = max(canGo[k][l], 3);
                    }
                }
            }
        }
    }

    vector<vector<pair<int, int> > > adjlist(node);

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            for(int bit = 0; bit < (1 << 5); bit++){

                //アナなら
                if(canGo[i][j] == 4) continue;

                int cost = canGo[i][j];
                int now_node = Map[i][j][bit];

                for(int h = 0; h < 4; h++){
                    int ni = i + di[h];
                    int nj = j + dj[h];

                    if(canGo[ni][nj] == 4) continue;
                    if(canGo[ni][nj] == 0) continue;

                    int next_bit = bit;
                    if(gold[ni][nj] != 0){
                        int idx = gold[ni][nj] - 1;
                        next_bit = next_bit & (~((1 << idx)));
                    }

                    int next_node = Map[ni][nj][next_bit];

                    adjlist[now_node].push_back(make_pair(cost, next_node));
                }
            }
        }
    }

    vector<int> result(node);
    int S = Map[si][sj][(1 << cnt) - 1];
    int G = Map[gi][gj][0];
    result = dijk(S, node, adjlist);
    cout << result[G] << endl;

    return 0;
}


Measured memory_bytes: 46408