#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = 4010;

int h1[N], h2[N], e[M], ne[M], w[M], n, m, idx;
int f[N][N];
PII q[N * N];
int ans = 1e9;

void add(int h[], int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int bfs(int fr, int to) {
    int hh = 0, tt = -1;
    f[fr][to] = 0;
    q[++ tt] = {fr, to};

    while (hh <= tt) {
        auto t = q[hh ++];
        int t1 = t.x, t2 = t.y;

        for (int i1 = h1[t1]; i1 != -1; i1 = ne[i1])
        for (int i2 = h1[t2]; i2 != -1; i2 = ne[i2]) {
            if (w[i1] != w[i2]) continue;
            int j1 = e[i1], j2 = e[i2];
            if (f[j1][j2] != -1)    continue;
            if (t1 == j2 && t2 == j1)
                ans = min(ans, f[t1][t2] + 1);  //入队不一定最小

            else if (j1 == j2)
                ans = min(ans, f[t1][t2] + 2);  //入队不一定最小

            f[j1][j2] = f[t1][t2] + 2;
            q[++ tt] = {j1, j2};
        }
    }
    if (ans == 1e9) return -1;
    return ans;
}
int main() {
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);
    memset(f, -1, sizeof f);

    cin >> n >> m;
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        char ch[2];
        cin >> a >> b >> ch;
        c = ch[0] - '\0';
        add(h1, a, b, c), add(h1, b, a, c);
        add(h2, a, b, c), add(h2, b, a, c);
    }

    cout << bfs(1, n);
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define P pair<int,char>
#define Tp tuple<int,int,int>
using Graph = vector<vector<P>>;

int main(){
    int N,M; cin >> N >> M;
    int a,b; char c;
    Graph g(N+1);
    rep(i,M){
        cin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    queue<tuple<int,int,int>> go;
    bool vis[N+1][N+1];
    rep(i,N+1){
        rep(j,N+1){
            vis[i][j] = false;
        }
    }
    vis[1][N] = true; go.push(make_tuple(0,1,N));
    int nowk = 0; bool fin = false;
    while(!go.empty()){
        auto p = go.front(); go.pop();
        a = get<1>(p); b = get<2>(p);
        int k = get<0>(p);
        if(k>nowk){
            nowk = k;
            if(fin){
                cout << 2*k-1 << endl; return 0;
            }
        }
        if(a==b){
            cout << 2*k << endl; return 0;
        }
        for(auto q:g[a]){
            int x = q.first; char c1 = q.second; int y;
            for(auto r:g[b]){
                y = r.first; char c2 = r.second;
                if(x==b&&y==a){
                    fin = true;
                }
                if(c1!=c2||vis[x][y]) continue;
                go.push(make_tuple(k+1,x,y)); vis[x][y] = true;
            }
        }
    }
    cout << -1 << endl;
}