#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define INF 100000
#define DEBUG 0

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<P,int> PI;
typedef pair<int,P> IP;

const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = {  0, 1, 0,-1 };
const int MAX_H = 100;
const int MAX_W = 100;
const int MAX_M = 5;		// 巻物の最大数
int H, W;
char f[MAX_H+1][MAX_W+1];	// フィールド
int  t[MAX_H+1][MAX_W+1];	// フィールドを移動する時間、穴が近くにあると遅くなる
int vis[MAX_H+1][MAX_W+1];	// bfs 探索用

int from_s[MAX_M+1], to_g[MAX_M+1], m2m[MAX_M+1][MAX_M+1]; // S から各巻物への距離、Gから各巻物への距離、各巻物の間の距離

void output (void ){
	
	rep (i, H ){
		rep (j, W ){
			cout << f[i][j];
		} // end rep
		cout << endl;
	} // end rep	
}
void output2 (void ){
	
	rep (i, H ){
		rep (j, W ){
			cout << (t[i][j] == -1 ? 4 : t[i][j] );
		} // end rep
		cout << endl;
	} // end rep	
}

int bfs (int sx, int sy, int ex, int ey ){

	priority_queue<IP, vector<IP>, greater<IP> > que;
	que.push (IP(0, P (sy, sx) ) );
	memset (vis, -1, sizeof (vis ) );
	vis[sy][sx] = 0;

	while (!que.empty() ){
		IP cur = que.top(); que.pop();
		int cn = cur.first;
		int cy = cur.second.first;
		int cx = cur.second.second;
		if (ex == cx && ey == cy ) return cn;

		rep (k, 4 ){
			int ny = cy + dy[k];
			int nx = cx + dx[k];
			if (ny < 0 || ny >= H || nx < 0 || nx >= W || f[ny][nx] == '#' ) continue;
			if (vis[ny][nx] == -1 || vis[ny][nx] > cn + t[cy][cx] ){
				vis[ny][nx] = cn + t[cy][cx];
				que.push (IP(cn + t[cy][cx], P (ny, nx ) ) );
			} // end if
		} // end rep
	} // end while	

	return INF;
}	


int main()
{
	memset (f, 0, sizeof (f ) );
	memset (from_s, 0, sizeof (from_s ) );
	memset (to_g, 0, sizeof (to_g ) );
	fill (t[0], t[0] + MAX_H*MAX_W+1, 1 );
	fill (m2m[0], m2m[0] + MAX_M*MAX_M+1, INF );
	ios_base::sync_with_stdio(0);
	cin >> W >> H;
	rep (i, H ) rep (j, W ) cin >> f[i][j];
	
	int sx, sy, ex, ey;		// S, G の位置
	vector<P> m; m.clear();	// 巻物の位置
	vector<P> hole; hole.clear();	// 穴の位置
	rep (i, H ) rep (j, W ){
		if (f[i][j] == 'S' ) sy = i, sx = j;
		if (f[i][j] == 'G' ) ey = i, ex = j;
		if (f[i][j] == 'M' ) m.push_back (P (j, i ) );
		if (f[i][j] == '#' ) hole.push_back (P (i, j ) );
	} // end rep	
	// 移動時間のマップを作成
	rep (k, hole.size() ){
		int i = hole[k].first;
		int j = hole[k].second;
		for (int row = max (i-2, 0 ); row <= min (i+2, H-1); row++ ){
			for (int col = max (j-2, 0 ); col <= min (j+2, W-1 ); col++ ){
				if (row == i && col == j ){
					continue;
				} // end if
				t[row][col] = max (t[row][col], 2 );
			} // end for
		} // end for
		for (int row = max (i-1, 0 ); row <= min (i+1, H-1); row++ ){
			for (int col = max (j-1, 0 ); col <= min (j+1, W-1 ); col++ ){
				if (row == i && col == j ){
					continue;
				} // end if
				t[row][col] = max (t[row][col], 3 );
			} // end for
		} // end for
	} // end rep	
	rep (k, hole.size() ){
		int i = hole[k].first;
		int j = hole[k].second;
		t[i][j] = -1;
	} // end rep
#if DEBUG
	output ();
	output2 ();
#endif
	// S から 各巻物までの最短距離を求める
	rep (i, m.size() ){
		from_s[i] = bfs (sx, sy, m[i].first, m[i].second );
		to_g[i]   = bfs (m[i].first, m[i].second, ex, ey );
	} // end rep

	// 各巻物間の最短距離を求める
	if (m.size() != 1 ){
		rep (i, m.size() ){
			rep (j, m.size() ){
				if (i == j ) continue;
				m2m[i][j] = bfs (m[i].first, m[i].second, m[j].first, m[j].second );
				m2m[j][i] = bfs (m[j].first, m[j].second, m[i].first, m[i].second );
			} // end rep
		} // end rep
	} // end if
	
	int res = INF;
	vector<int> a(m.size(), 0 );
	rep (i, m.size() ) a[i] = i;
	do{
		int curr = from_s[a[0]];
		rep (i, m.size()-1 ){
			curr += m2m[a[i]][a[i+1]];
		} // end rep
		curr += to_g[a[m.size()-1]];
		res = min (res, curr );
	}while (next_permutation (ALL (a ) ) );

	cout << res << endl;
	
	return 0;
}

Measured memory_bytes: 1336