#include<bits/stdc++.h>
using namespace std;
#define M 500000
typedef long long ll;
typedef unsigned long long ull;
inline ll read() {
	char ch;
	ll f = 1, res = 0;
	while ((ch = getchar()) < '0' || ch > '9')
		if (ch == '-') f = -1;
	while (ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return f * res;
}
inline void pt(ll u,ll mod) {
	printf("%lld", u);
	if (mod == 1)
		putchar(' ');
	else if (mod == 2)
		putchar('\n');
}

bool con[1010][1010]={false};
ll mat[1010][1010];
vector<ll>e[M][26];
ll m,n;
ll ans=1e15;
char c;
//struct node {
//	ll x, y;
//};

void dfs(ll inx1,ll inx2,ll v ) {
//	pt(inx1,inx2);
	if (v >= ans)
		return;
	mat[inx1][inx2] = v;
	if (con[inx1][inx2]) {
		if (inx1 == inx2)
			ans = v;
		else
			ans = v + 1;
	}
	for (ll i = 0; i < 26; i++) {
		for (auto u:e[inx1][i])
			for (auto p:e[inx2][i]) {
				if (mat[u][p] > v + 2)
					dfs(u, p, v + 2);
			}
	}
}
int main() {
	//freopen("../in", "r", stdin);
	//freopen("../out", "w", stdout);
	memset(mat, 0x3f, sizeof(mat));
	m = read(), n = read();
	ll a, b;
	for (ll i = 0; i < n; i++) {
		a = read(), b = read();
		scanf("%c", &c);
		con[a][b] = true;
		con[b][a] = true;
		e[a][c - 'a'].push_back(b);
		e[b][c - 'a'].push_back(a);
	}
	for (ll i = 1; i <= m; i++)
		con[i][i] = true;
	dfs(1, m, 0);
	if (ans > 1e14)
		pt(-1, 2);
	else
		pt(ans, 2);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define setbits(n) __builtin_popcountll(n)
#define mkunique(a) sort(a.begin(),a.end()); a.resize(unique(a.begin(),a.end())-a.begin());
#define print(s) for(ll u: s) cout<<u<<" "; cout<<"\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
 
const int N=1e5+10;
vector<pair<ll,pair<ll,ll>>> a[N];
 
int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll TT=clock();
 
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v,c,d;
        cin>>u>>v>>c>>d; u--,v--;
        a[u].pb({v,{c,d}});
        a[v].pb({u,{c,d}});
    }
    vector<ll> d(n,mod*mod);
    d[0] = 0;
    set<pair<ll,ll>> s;
    s.insert({0,0});
    while(!s.empty()){
        ll v = s.begin()->ss;
        s.erase(s.begin());
        for(auto ed: a[v]){
            ll u = ed.ff, c = ed.ss.ff, dd = ed.ss.ss;
            ll t = d[v];
            ll cost = t + c + dd/(t+1);
            ll opt = max(t,(ll)sqrt(dd) - 1);
            cost = min(cost, opt + c + dd/(opt+1));
            opt++;
            cost = min(cost, opt + c + dd/(opt+1));
            if(cost < d[u]){
                s.erase({d[u],u});
                d[u] = cost;
                s.insert({d[u],u});
            }
        }
    }
    if(d[n-1]==mod*mod)
        cout<<-1;
    else
        cout<<d[n-1];
 
 
    cerr<<"\n\nTIME: "<<(long double)(clock()-TT)/CLOCKS_PER_SEC<<" sec\n";
    TT = clock();
    return 0;
}