#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;
}

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

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

template<typename T1,typename T2>ostream& operator<<(ostream& os,const pair<T1,T2>& a) {os << "(" << a.first << ", " << a.second << ")";return os;}

const char newl = '\n';

template <typename T>
void dijkstra(int s,vector<vector<pair<int,T>>>& edges,vector<T>& dist) {
    priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> que;
    dist[s] = 0;
    que.push(make_pair(0,s));
    while (!que.empty()) {
        pair<ll,int> p = que.top();
        que.pop();
        int v =  p.second;
        if (dist[v] < p.first) continue;
        for (pair<int,T>& e : edges[v]) {
            if (dist[e.first] > dist[v]+e.second) {
                dist[e.first] = dist[v]+e.second;
                que.push(make_pair(dist[e.first],e.first));
            }
        }
    }
}

int main() {
    int n,m;
    cin >> n >> m;
    vector<P> a[26];
    for (int i = 0;i < m;++i) {
        int u,v;char c;
        cin >> u >> v >> c;
        a[c-'a'].push_back(make_pair(u-1,v-1));
    }
    vector<vector<P>> edges(n*n);
    for (int c = 0;c < 26;++c) {
        for (int i = 0;i < a[c].size();++i) for (int j = 0;j < a[c].size();++j) {
            P &p = a[c][i];
            P &q = a[c][j];
            edges[p.first*n+q.first].push_back(make_pair(p.second*n+q.second,1));
            edges[p.second*n+q.second].push_back(make_pair(p.first*n+q.first,1));
            edges[p.second*n+q.first].push_back(make_pair(p.first*n+q.second,1));
            edges[p.first*n+q.second].push_back(make_pair(p.second*n+q.first,1));
        }
    }
    vector<int> dist(n*n,1e9);
    dijkstra<int>(n-1,edges,dist);
    cout << (dist[(n-1)*n] < 1e9 ? dist[(n-1)*n] : -1) << newl;
}