#define ll long long
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > a[100005];
ll dp[20][500000];
ll n,c;
ll rec(ll i,ll mask){
    ll j,k,s=0,p;
    if(dp[i][mask]!=-1) return dp[i][mask];
    for(j=0;j<a[i-1].size();j++){
        p=0;
        for(k=0;k<18;k++){
            if(mask>>k&1){
                if(k<=a[i-1][j].first) p++;
            }
        }
        if(p>a[i-1][j].second) return dp[i-1][mask]=0;
    }
    if(i==n) return 1;
    for(j=0;j<n;j++){
        if(((mask>>j)&1)!=1){
            s+=rec(i+1,mask|1<<j);
        }
    }
    return dp[i][mask]=s;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll i,j,k,m,x,y,z,t;
    cin>>n>>m;
    c=pow(2,n)-1;
    for(i=0;i<m;i++){
        cin>>x>>y>>z;
        a[x-1].push_back({y-1,z});
    }
    memset(dp,-1,sizeof(dp));
    k=rec(0,0);
    cout<<k<<endl;
}

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define Type int
#define rept(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,a) rept(i,0,a)
#define fi first
#define se second
#define ii pair<int,int>
//#define 
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
string s[2022];
vector<ii>vec[28];
ii st,ed;
int n,m;
int use[2022][2022],dist[2022][2022];
signed main()
{
	cin>>n>>m;
	rep(i,n){
		cin>>s[i];
		rep(j,m){
			if (s[i][j]=='S')
				st=mp(i,j);
			if (s[i][j]=='G')
				ed=mp(i,j);
			if (islower(s[i][j]))
				vec[s[i][j]-'a'].pb(mp(i,j));
		}
	}
	queue<ii>q;
	q.push(st);
	use[st.fi][st.se]=1;
	rep(i,n)rep(j,m)dist[i][j]=1000000000;
	dist[st.fi][st.se]=0;
	while (!q.empty()){
		ii cur=q.front();q.pop();
		//cout<<'('<<cur.fi<<','<<cur.se<<')'<<'\n'; 
		rep(i,4){
			int nx=cur.fi+dx[i],ny=cur.se+dy[i];
			if (nx<n && nx>=0 && ny<m && ny>=0 && !use[nx][ny] && s[nx][ny]!='#'){
				//cout<<'('<<nx<<','<<ny<<')'<<'\n'; 
				dist[nx][ny]=dist[cur.fi][cur.se]+1;
				q.push(mp(nx,ny));
				use[nx][ny]=1;
				if (islower(s[nx][ny])){
					int tt=s[nx][ny]-'a';
					rep(j,sz(vec[tt])){
						if (vec[tt][j]==mp(nx,ny)){
							vec[tt].erase(vec[tt].begin()+j);
							break;
						}
					}
				}
			}
		}
		//cout<<"OK\n";
		if (islower(s[cur.fi][cur.se])){
			int tt=s[cur.fi][cur.se]-'a';
			rep(j,sz(vec[tt])){
				int nx=vec[tt][j].fi,ny=vec[tt][j].se;
				dist[nx][ny]=dist[cur.fi][cur.se]+1;
				q.push(mp(nx,ny));
				use[nx][ny]=1;
			}
			vec[tt]=vector<ii>(0);
		}
	}
	cout<<(dist[ed.fi][ed.se]==1000000000?-1:dist[ed.fi][ed.se]);
	re 0;
}
