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

#define INF 1234567890
#define ll long long

int N, M;
vector<pair<int, int> > g[2020], h[2020];
int dist[2020];

int Dijkstra(int S)
{
	memset(dist, 0x3f, sizeof(dist));
	priority_queue<pair<int, int> > pq;
	pq.push({0, S}); dist[S] = 0;
	while(!pq.empty())
	{
		int d = -pq.top().first, n = pq.top().second;
		pq.pop();

		if (dist[n] < d) continue;

		for(auto &it : h[n])
		{
			int next = it.first, nd = d+it.second;
			if (dist[next] <= nd) continue;
			pq.push({-nd, next}); dist[next] = nd;
		}
	}
	int ret = 0x3f3f3f3f;
	for(auto &it : g[S])
	{
		int next = it.first;
		ret = min(ret, it.second+dist[next]);
	}
	if (ret == 0x3f3f3f3f) ret = -1;
	return ret;
}

int main()
{
	scanf("%d %d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		g[a].push_back({b, c});
		h[b].push_back({a, c});
	}
	for(int i=1; i<=N; i++)
		printf("%d\n", Dijkstra(i));
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif


const int MAXN = 5e6;

vector<int> aa[MAXN];
vector<int> ww[MAXN];

int H, W;
vector<vector<char>> grid;

vector<pair<int,int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool inside(int i, int j) {
    if (i < 0 or H <= i) return false;
    if (j < 0 or W <= j) return false;
    return true;
}

int grid2num(int i, int j) {
    return i*W + j;
}

void amica() {
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        int num = grid2num(i,j);
        if (grid[i][j] == '#') continue;
        for (auto pp : dir) {
            int u = i + pp.first, v = j + pp.second;
            if (!inside(u,v)) continue;
            if (grid[u][v] == '#') continue;
            aa[num].push_back(grid2num(u,v));
            ww[num].push_back(2);
            //~ cout << num << " " << grid2num(u,v) << endl;
        }
        int l = grid[i][j] - 'a';
        if (l < 0 or l > 25) continue;
        aa[num].push_back(H*W + l);
        ww[num].push_back(1);
        aa[H*W + l].push_back(num);
        ww[H*W + l].push_back(1);
    }
    
}


const int INF = 1e9;

int dijkstra(int start, int end) {
    vector<int> dist(H*W + 50, INF);
    vector<bool> fatto(H*W + 50, false);
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int v = pq.top().second;
        pq.pop();
        if (fatto[v]) continue;
        //~ cout << v << endl;
        fatto[v] = true;
        for (int i = 0; i < (int)aa[v].size(); i++) {
            int a = aa[v][i], w = ww[v][i];
            if (fatto[a]) continue;
            if (dist[a] <= dist[v] + w) continue;
            dist[a] = dist[v] + w;
            pq.push({dist[a], a});
        }
    }
    //~ cout << endl << start << " " << end << endl;
    if (dist[end] == INF) return -2;
    return dist[end];
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    cin >> H >> W;
    grid.resize(H, vector<char>(W));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> grid[i][j];
    amica();

    int start, end;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (grid[i][j] == 'S') start = grid2num(i, j);
        if (grid[i][j] == 'G') end = grid2num(i, j);
    }
    cout << dijkstra(start, end)/2 << "\n";
}
