#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
using namespace std;
const int M=1005;
struct node {
	int to,c;
};
vector <node> E[M];
bool vis[M][M];
struct PR {
	int l,r,dis;
	bool operator <(const PR &a)const {return dis>a.dis;}
};
priority_queue <PR> Q;
int main() {
	int n=read(),m=read();
	char s[5];
	rep(i,1,m){
		int u=read(),v=read();scanf("%s",s+1);
		E[u].push_back((node){v,s[1]});
		E[v].push_back((node){u,s[1]});
		Q.push((PR){u,v,1});
		Q.push((PR){v,u,1});
	}
	rep(i,1,n)Q.push((PR){i,i,0});
	while(!Q.empty()){
		PR top=Q.top();Q.pop();
		if(top.l==1&&top.r==n){
			printf("%d\n",top.dis);
			return 0;
		}
		if(vis[top.l][top.r])continue;
		vis[top.l][top.r]=1;
		rep(i,0,E[top.l].size()-1){
			int to=E[top.l][i].to,c=E[top.l][i].c;
			rep(j,0,E[top.r].size()-1){
				int t=E[top.r][j].to,cc=E[top.r][j].c;
				if(c!=cc)continue;
				Q.push((PR){to,t,top.dis+2});
			}
		}
	}
	puts("-1");
	return 0;
}

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

typedef pair<int,int> pii;
typedef pair<string,int> psi;
typedef pair<int,string> pis;
typedef array<int,2> aii;
typedef array<int,3> aiii;
typedef array<int,4> aiiii;
typedef unsigned long long ull;
typedef long long int ll;
typedef array<ll,2> all;
typedef array<ll,3> alll;
typedef array<ll,4> allll;

#define pb push_back
#define ff first
#define ss second
#define MAX 1000005
#define MOD 1000000007
#define INF 1e9+100
vector<int>adj[MAX];
int xMove[] = { 0,1,0,-1,1,1,-1,-1, 2, 2, -2, -2, 1, 1, -1, -1 };
int yMove[] = { 1,0,-1,0,1,-1,1,-1, 1, -1, 1, -1, 2, -2, 2, -2 };

void add_edge(int a, int b, int c, int d, int n)
{
    int u=(a-1)*n+b,v=(c-1)*n+d;
    adj[u].pb(v);
    adj[v].pb(u);
}

int dist[MAX];

void bfs(int s)
{
    memset(dist,-1,sizeof dist);

    queue<int> q;
    q.push(s);
    dist[s]=0;

    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int v: adj[u])
        {
            if(dist[v]==-1)
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.txt","w",stdout);
    cin.tie(0),cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);
    int TC=1;
    int n,m,k,q;
    //cin>>TC;
    for(int t1=1; t1<=TC; t1++)
    {
        cin>>n>>m;
        vector<aiii> edges(m);
        int mp[n*n+1];
        memset(mp,-1,sizeof mp);
        for(auto &[u,v,c]: edges)
        {
            char c1;
            cin>>u>>v>>c1;
            c=c1;
            mp[(u-1)*n+v]=1;
            mp[(v-1)*n+u]=1;
        }

        for(auto [a,b,c1]: edges)
        {
            for(auto [c,d,c2]: edges)
            {
                if(c2==c1)
                {
                    add_edge(a,c,b,d,n);
                    add_edge(c,a,d,b,n);
                    add_edge(a,d,b,c,n);
                    add_edge(d,a,c,b,n);
                }
            }
        }

        bfs(n);
        int mn=INF;
        for(int i=1;i<=n*n;i++)
        {
            if(dist[i]!=-1)
            {
                int r=i%n;
                int d=(i-r)/n;
                if(d+1==r)
                    mn=min(mn,2*dist[i]);
                else if(mp[i]==1)
                    mn=min(mn,2*dist[i]+1);
            }
        }

        cout<<(mn==INF?-1:mn)<<endl;
    }

    return 0;
}
