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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vz;
typedef vector<vz> vvz;
typedef pair<ll, ll> pll;
#define sz(x) ll((x).size())
#define fo(i,n) for(ll i=0; i<(n); i++)
#define FO(i,a,b) for(ll i=(a); i!=(b); i+=(b)>(a)?1:-1)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(c) c.begin(), c.end()
#define F first
#define S second
#define os(x) cout<<x<<' '
#define on(x) cout<<x<<"\n"
#define nl cout<<"\n"
#define maxe(x) max_element(all(x))-(x).begin()
#define mine(x) min_element(all(x))-(x).begin()
const ll P=998244353;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("C:\\Users\\ASISH\\Desktop\\coding\\input1.txt", "r", stdin);
	freopen("C:\\Users\\ASISH\\Desktop\\coding\\output1.txt", "w", stdout);
#endif

	ll n, m, mi=10000000;
	cin>>n>>m;
	vll a(n*m);
	fo(i, n*m){
		cin>>a[i];
		mi=min(mi, a[i]);
	}
	ll ans=0;
	fo(i, n*m){
		ans+=a[i]-mi;
	}
	on(ans);
	cerr << "Time : " << ((double)clock()) / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
template <class T = int>
using V = vector<T>;
template <class T = int>
using VV = V<V<T>>;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;

struct edge{
    int to, c;
    edge(int to, int c): to(to), c(c) {}
};

const int INF = 1<<30;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    VV<edge> g(n);
    rep(i,m){
        int a, b; char c;
        cin >> a >> b >> c;
        a--, b--;
        g[a].eb(b,c-'a');
        g[b].eb(a,c-'a');
    }
    VV<int> dp(n, V<int>(n, INF));
    queue<pii> que;
    auto push = [&](int a, int b, int x){
        if(dp[a][b] != INF) return;
        dp[a][b] = x;
        que.emplace(a,b);
    };
    push(0,n-1,0);
    while(!que.empty()){
        int a = que.front().first, b = que.front().second;
        que.pop();
        for(auto ea : g[a]) for(auto eb : g[b]){
            if(ea.c != eb.c) continue;
            push(ea.to, eb.to, dp[a][b] + 1);
        }
    }
    int ans = dp[n-1][0];
    if(ans == INF) ans = -1;
    cout << ans << endl;
}