#include <bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=1e3+5;
const int inf=0x3f3f3f3f;
template<class T>inline void read(T &x) {
	T f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
vector<int> to[26][N];
int e[N][N];
int dis[N][N],n,m,a,b,ad,cnt[N];
char s[5];
queue<pii> q;
pii tp;
int main() {
	read(n); read(m);
	rep(i,1,m) {
		read(a); read(b);
		scanf("%s",s+1);
		ad=s[1]-'a';
		e[a][b]=1; e[b][a]=1;
		to[ad][a].emplace_back(b);
		to[ad][b].emplace_back(a);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1][n]=0;
	q.push(mp(1,n));
	int Ans=inf;
	while(!q.empty()) {
		tp=q.front(); q.pop();
		rep(i,0,25) {
			for(int v1:to[i][tp.fi]) for(int v2:to[i][tp.se]) {
				if(dis[v1][v2]>(dis[tp.fi][tp.se]+2)) {
					dis[v1][v2]=dis[tp.fi][tp.se]+2;
					q.push(mp(v1,v2));
				}
			}
		}
	}
	rep(i,1,n) Ans=std::min(Ans,dis[i][i]);
	rep(i,1,n) rep(j,1,n) if(e[i][j]) Ans=std::min(Ans,dis[i][j]+1);
	if(Ans==inf) puts("-1");
	else printf("%d\n",Ans);
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define LOL cout << '\n';
#define kill(x) {cout << (x) << '\n'; return;}
#define sz(x) ((int)x.size())
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN
#define deb(x) cout << "[" << (#x) << "=" << x << "]" << '\n'
#define deb2(x,y) cout << "[" << (#x) << "=" << x << "] [" << (#y) << "=" << y << "]" << '\n'
#define deb3(x,y,z) cout << "[" << (#x) << "=" << x << "] [" << (#y) << "=" << y << "] [" << (#z) << "=" << z << "]" << '\n'

void solve(){
  int a,b,c,d; cin>>a>>b>>c>>d;
  int x=max(a,b),y=min(c,d);
  kill(x-y);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int _ = 1; // cin >> _;
  for(int i = 1 ; i <= _ ; i++){
    // cout << "\nCase #" << i << ": \n";
    solve();
  }
  return 0;
}

// 1.77245