#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

bool chmin(ll &a, ll b) {if(a>b){a=b; return 1; } return 0; }
typedef pair<ll, int> P;
struct edge {int to; ll cost; };

struct Graph {
	private:
		int n;
		vector<ll> d;
		vector<vector<edge>> es;
	public:
		Graph(int _n): n(_n), d(_n), es(_n) {}
		void add_edge(int from, int to, ll cost) {
			edge e;
			e.to = to, e.cost = cost;
			es[from].push_back(e);
		}
		void dijkstra(int s) {
			rep(i,n) d[i] = LINF;
			d[s] = 0;
			priority_queue<P, vector<P>, greater<P>> q;
			q.push(P(0, s));
			while (!q.empty()) {
				P p = q.top(); q.pop();
				int v = p.second;
				if (d[v] < p.first) continue;
				for (edge e: es[v]) {
					if (chmin(d[e.to], p.first + e.cost)) {
						q.push(P(d[e.to], e.to));
					}
				}
			}
		}
		ll get_dist(int u) {
			return d[u];
		}
};

int h, w;
int f(int i, int j) {
	return i*w+j;
}
 

int main() {
	cin >> h >> w;
	vector<string> g(h);
	rep(i,h) cin >> g[i];
	Graph dij(h*w+26);
	int ps = -1, pg = -1;
	rep(i,h) {
		rep(j,w) {
			if (g[i][j] == '#') continue;
			int cur = f(i,j);
			if (g[i][j] == 'S') ps = cur;
			if (g[i][j] == 'G') pg = cur;
			rep(d, 4) {
				int ni = i + dy[d];
				int nj = j + dx[d];
				if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
				if (g[ni][nj] == '#') continue;
				int nxt = f(ni,nj);
				dij.add_edge(cur, nxt, 1);
			}
			if ('a' <= g[i][j] && g[i][j] <= 'z') {
				int spr = h*w + (g[i][j] - 'a');
				dij.add_edge(cur, spr, 1);
				dij.add_edge(spr, cur, 0);
			}
		}
	}
	dij.dijkstra(ps);
	if (dij.get_dist(pg) == LINF) cout << -1 << endl;
	else cout << dij.get_dist(pg) << endl;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<(a)<<endl
#define dumparr(a,n) cerr<<#a<<"["<<(n)<<"]="<<(a[n])<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

pll operator+(pll a,pll b){
  return pll(a.first+b.first,a.second+b.second);
}
pll operator-(pll a,pll b){
  return pll(a.first-b.first,a.second-b.second);
}
pll operator*(ll a,pll b){
  return pll(b.first*a,b.second*a);
}
const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


int main(){
  cout<<setprecision(1000);
  ll N,M;
  cin>>N>>M;
  vector<ll> dp(1LL<<N);
  vector<vector<pll>> cond(N);
  REP(M){
    ll x,y,z;
    cin>>x>>y>>z;
    --x;--y;
    cond[x].push_back(pll(y,z));
  }
  auto f=[](ll num,ll y,ll z){
    ll mask=(1LL<<(y+1))-1;
    num&=mask;
    return __builtin_popcountll(num)<=z;
  };
  dp[0]=1;
  For(j,(1LL<<N)){
    ll n=__builtin_popcountll(j);
    if(n==N)continue;
    ll cur=1;
    REP(N){
      if((cur&j)==0){
        ll jj=(j|cur);
        ([&]() {
          FOR(cidx, n, N)
          {
            for (auto &&[y, z] : cond[cidx])
            {
              if (!f(jj, y, z))
              {
                return;
              }
            }
          }
          dp[jj]+=dp[j];
        })();
      }
      cur<<=1;
    }
  }
  dump(dp);
  cout<<dp[(1LL<<N)-1]<<endl;
  return 0;
}
