#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using cd = complex<ld>;

struct edge {
  int from, to;
  char c;
};

vector<edge> g[1000];
bool calced[1000][1000];
int dp[1000][1000];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    char c;
    cin >> u >> v >> c;
    --u;
    --v;
    g[u].push_back({u, v, c});
    g[v].push_back({v, u, c});
  }
  queue<pii> pq;
  for (int i = 0; i < n; i++) {
    calced[i][i] = true;
    pq.emplace(i, i);
  }
  for (int i = 0; i < n; i++) {
    for (edge e : g[i]) {
      if (e.to != i) {
        calced[i][e.to] = true;
        dp[i][e.to] = 1;
        pq.emplace(i, e.to);
      }
    }
  }
  while (!pq.empty()) {
    auto[u, v] = pq.front();
    pq.pop();
    for (char c = 'a'; c <= 'z'; c++) {
      for (auto e1 : g[u]) {
        if (e1.c != c) {
          continue;
        }
        for (auto e2 : g[v]) {
          if (e2.c != c) {
            continue;
          }
          if (!calced[e1.to][e2.to]) {
            dp[e1.to][e2.to] = dp[u][v] + 2;
            calced[e1.to][e2.to] = true;
            pq.emplace(e1.to, e2.to);
          }
        }
      }
    }
  }

  cout << (calced[0][n - 1] ? dp[0][n - 1] : -1);
  return 0;
}

#include<bits/stdc++.h>
#define M 100005
typedef long long ll;
using namespace std;
bool f2;
char IO;
int rd(){
	int num=0;bool f=0;
	while(IO=getchar(),IO<48||IO>57)if(IO=='-')f=1;
	do num=(num<<1)+(num<<3)+(IO^48);
	while(IO=getchar(),IO>=48&&IO<=57);
	return f?-num:num;
}
int n,m;
struct node{
	int v;ll C,D;
};
vector<node> E[M];
ll dis[M];
bool vis[M];
struct Data{
	int idx;ll dis;
	bool operator<(const Data &_)const{
		return dis>_.dis;
	}
};
priority_queue<Data> Q;
void Dijkstra(){
	memset(dis,127,sizeof(dis));
	dis[1]=0;Q.push((Data){1,0});
	int u,v;ll tmp,t;
	while(!Q.empty()){
		u=Q.top().idx;
		Q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<E[u].size();++i){
			t=sqrt(E[u][i].D);v=E[u][i].v;
			if(dis[u]>=t){
				tmp=dis[u]+E[u][i].C+E[u][i].D/(dis[u]+1);
			}else{
				tmp=t+E[u][i].C+E[u][i].D/(t+1);
			}
			if(tmp<dis[v]){
				dis[v]=tmp;
				if(!vis[v])
					Q.push((Data){v,dis[v]});
			}
		}
	}
	if(vis[n]==0){
		cout<<-1;
	}else cout<<dis[n];
	
}
bool f1;
int main(){
//	cout<<(&f1-&f2)/1024.0/1024.0<<endl;
	n=rd();m=rd();
	for(int i=1,u,v,C,D;i<=m;++i){
		u=rd(),v=rd(),C=rd(),D=rd();
		E[u].push_back((node){v,C,D});
		E[v].push_back((node){u,C,D});
	}
	Dijkstra();
	return 0;
}