#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll> ;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define inf 1LL<<60;
ll min(ll a,ll b){return a>=b ? b:a;}
ll max(ll a,ll b){return a>=b ? a:b;}

ll dist[1<<18];

typedef struct{
    ll to;
    ll c;
    ll d;
}town;

vector<town> G[1LL<<18];

ll func(ll t,ll d){
    ll rd=sqrt(d);
    ll ret=d/(t+1);
    for (ll i=-10;i<=10;++i){
        if (rd+i-t-1<0) continue;
        ll k=rd-t+i-1+d/(rd+i);
        ret=min(ret,k);
    }
    return ret;
}

void dijkstra(ll st){
    priority_queue<P,vector<P>,greater<>> q;
    dist[st]=0;
    q.push(P(0,st));
    while (!q.empty()){
        ll D=q.top().first;
        ll pos=q.top().second;q.pop();
        if (dist[pos]<D) continue;
        rep(i,(ll)G[pos].size()){
            ll to=G[pos][i].to;
            ll cost=G[pos][i].c;
            ll di=G[pos][i].d;
            ll ct=func(dist[pos],di);
            if (dist[to]>dist[pos]+ct+cost){
                dist[to]=ct+cost+dist[pos];
                q.push(make_pair(dist[to],to));
            }
        }
    }
}

int main(){
    ll n,m;
    cin >> n >> m;
    rep(i,m){
        ll a,b,c,d;
        cin >> a >> b >> c >>d;
        a--;b--;
        G[a].push_back(town({b,c,d}));
        G[b].push_back(town({a,c,d}));
    }
    rep(i,n+1) dist[i]=1LL<<60;
    dijkstra(0);
    if (dist[n-1]==1LL<<60){
        cout << -1 << endl;
    }
    else cout << dist[n-1] << endl;
}




#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;

int dx[] = {0, 1, 0, -1};

int main(){
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  vector<vector<int>> v(26);
  vector<vector<int>> dp(h, vector<int>(w, INF));
  priority_queue<P, vector<P>, greater<P>> que;
  int gh = -1, gw = -1;

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (s[i][j] == '#' || s[i][j] == '.') continue;
      if (s[i][j] == 'S') {
        que.push(make_pair(0, i * w + j));
        dp[i][j] = 0;
      } else if (s[i][j] == 'G') {
        gh = i; gw = j;
      } else {
        v[s[i][j] - 'a'].emplace_back(i * w + j);
      }
    }
  } 
  vector<int> ok(26, 0);

  while (!que.empty()) {
    auto p = que.top(); que.pop();
    int i = p.second / w, j = p.second % w;
    if (dp[i][j] < p.first) continue;
    for (int k = 0; k < 4; k++) {
      int ni = i + dx[k], nj = j + dx[(k + 1) % 4];
      if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
      if (s[ni][nj] == '#') continue;
      if (dp[ni][nj] > dp[i][j] + 1) {
        dp[ni][nj] = dp[i][j] + 1;
        que.push(make_pair(dp[ni][nj], ni * w + nj));
      }
    }
    if (s[i][j] == '.' || s[i][j] == 'S' || s[i][j] == 'G') continue;
    if (ok[s[i][j] - 'a']) continue;
    for (auto e : v[s[i][j] - 'a']) {
      if (dp[e / w][e % w] > dp[i][j] + 1) {
        dp[e / w][e % w] = dp[i][j] + 1;
        que.push(make_pair(dp[e / w][e % w], e));
      }
    }
    ok[s[i][j] - 'a'] = 1;
  }
  
  cout << (dp[gh][gw] == INF ? -1 : dp[gh][gw]) << endl;
  return 0;
}