#include<bits/stdc++.h>
using namespace std;
#define SPEED ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define READ freopen("out.txt","r",stdin)
#define WRITE freopen("out.txt","w",stdout);
#define pb push_back
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define sf(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define sd(x) scanf("%lf",&x);
#define pii pair<int,int>
#define pLL pair<long long,long long>
#define pDB pair<double,double>
#define ff first
#define sn second
#define PRINT_CASE  printf("Case %d: ",tc++)
#define PRINT_CASENL  printf("Case %d:\n",tc++)
#define lnd tree[ind<<1]
#define rnd tree[(ind<<1)+1]
#define cnd tree[ind]
#define lndp b,(b+e)>>1,(ind<<1)
#define rndp ((b+e)>>1)+1,e,(ind<<1)+1
#define IN(a,x,y) (a>=x && a<=y)
#define popcountL __builtin_popcountll
#define popcount __builtin_popcount
/// int other=mask^((1<<n)-1);
typedef long long ll;
typedef long long int lln;
typedef unsigned long long int ull;
ll INF=1<<28;
//typedef long long lld;
const double pi=acos(-1.0);
int fx[]={1,-1,0,0}; //direction array
int fy[]={0,0,1,-1};
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int knight[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1};
const long double EPS=1e-7;
//#define INF 10000

ll lcm(ll a,ll b)
{
    return a/__gcd(a,b)*b;
}
//struct compare
//{
//  bool operator()(const int& l, const int& r)
//  {
//      return l>r;
//  }
//};

const int mx=201050;
const int mod=998244353;
//const int mod=1e9+7;
// Including Policy Based DS
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//
//////cout<<*X.find_by_order(1)<<endl;
////cout<<X.order_of_key(-5)<<endl;
int vis[mx];
int color[mx];
vector<pii>G[mx];
void dfs(int node,int last,int bosanolagbe)
{
    vis[node]=1;
    int bosanohoise=-1;
    if(bosanolagbe!=0)
    {
        color[node]=bosanolagbe;
        bosanohoise=bosanolagbe;
    }
    set<int>st;
    st.insert(last);
    st.insert(0);
    for(auto x:G[node])
    {
        if(!vis[x.ff])
        {
            if(bosanohoise==-1)
            {
                if(x.sn!=last)
                {
                    color[node]=x.sn;
                    bosanohoise=x.sn;
                    dfs(x.ff,x.sn,0);
                }
                else
                {
                    st.insert(x.sn);
                    dfs(x.ff,0,x.sn);
                }
            }
            else
            {
                if(x.sn==bosanohoise)
                {
                    dfs(x.ff,x.sn,0);
                }
                else
                {
                    dfs(x.ff,bosanohoise,x.sn);
                }

            }
        }
    }
    if(bosanohoise==-1)
    {
        int c=1;
        while(st.find(c)!=st.end())
        {
            c++;
        }
        color[node]=c;
    }
}
int main()
{
//    SPEED;

    int t=1;
//    sf(t);
    while(t--)
    {
        int n,m;
        sf2(n,m);
        int x,y,z;
        for(int i=0;i<m;i++)
        {
            sf3(x,y,z);
            G[x].pb({y,z});
            G[y].pb({x,z});
        }
        dfs(1,0,0);

        for(int i=1;i<=n;i++)
        {
            if(color[i]==0)
            {
                cout<<"No"<<endl;
//                return 0;
            }
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",color[i]);
        }
    }
    return 0;
}

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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)((n)-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p){
    return o << "(" << p.first << ", " << p.second << ")";
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

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

int h,w;
vvi d;
vector<string> g;
vector<pii> ts[26];
void bfs(pii s){
    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> Q;
    Q.emplace(0,s);
    d[s.fi][s.se] = 0;
    while(!Q.empty()){
        pair<int,pii> p = Q.top(); Q.pop();
        int i = p.se.fi;
        int j = p.se.se;
        char c = g[i][j] - 'a';
        if(0 <= c && c <= 26 && ts[c].size() > 0){
            for(auto t : ts[c]){
                int ti = t.fi;
                int tj = t.se;
                if(d[ti][tj] > d[i][j] + 1){
                    d[ti][tj] = d[i][j] + 1;
                    Q.emplace(d[ti][tj],pii(ti,tj));
                }
            }
            while(ts[c].size() > 0) ts[c].pop_back();
        }
        rep(k,4){
            int ni = i + di[k];
            int nj = j + dj[k];
            if(ni < 0 || h <= ni) continue;
            if(nj < 0 || w <= nj) continue;
            if(g[ni][nj] == '#') continue;
            if(d[ni][nj] > d[i][j] + 1){
                d[ni][nj] = d[i][j] + 1;
                Q.emplace(d[ni][nj],pii(ni,nj));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    cin >> h >> w;
    g = vector<string>(h);
    d = vvi(h,vi(w, INF));
    pii start,goal;
    rep(i,h){
        cin >> g[i];
        rep(j,w){
            char c = g[i][j];
            if('a' <= c && c <= 'z'){
                ts[c-'a'].emplace_back(i,j);
            }
            if(c == 'S') start = pii(i,j);
            if(c == 'G') goal = pii(i,j);
        }
    }
    bfs(start);
    if(d[goal.fi][goal.se] == INF) cout << -1 << endl;
    else cout << d[goal.fi][goal.se] << endl;
    return 0;
}