#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <time.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define per(i, n) for(int i = n - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define vd vector<double>
#define vvd vector<vd>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdi pair<double, int>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using namespace std;
constexpr int n = 20;
int m;
vector<string> s;
vector<deque<string>> ss(n + 1);
vvi board(n, vi(n));
void tekitou_sort(){
	rep(i, n){
		int nokori = n;
		while(true){
			bool found = false;
			for(int j = nokori; j >= 0; j--) if(!ss[j].empty()){
				found = true;
				rep(k, j) board[i][n-nokori+k] = ss[j][0][k] - 'A';
				nokori -= j;
				ss[j].pop_front();
				break;
			}
			if(!found) break;
		}
	}
}
void inputs(){
	cin >> m >> m;
	s.resize(m);
	rep(i, m) cin >> s[i];
}
int main(){
	srand(time(NULL));
	inputs();
	rep(i, m) ss[s[i].size()].push_back(s[i]);

	rep(i, n) rep(j, n) board[i][j] = rand() % 8;
	tekitou_sort();

	rep(i, n){
		rep(j, s[i].size()) board[i][j] = s[i][j] - 'A';
	}
	rep(i, n){
		rep(j, n) printf("%c", board[i][j] + 'A');
		printf("\n");
	}
}
#include <bits/stdc++.h>
using namespace std;

#define FasterIO ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define ll long long
#define ff first
#define ss second
#define pi pair<int, int>

const int MX=1e3+10;
const ll mod=1e9+7;


int d[MX][MX], vis[MX][MX], ad[MX][MX];
vector<int>g[MX][26];

void bfs(int n)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) d[i][j]=1e9;
    }

    queue<pi>q; q.push({1, n}), d[1][n]=0, vis[1][n]++;

    while(q.size())
    {
        int x=q.front().ff, y=q.front().ss; q.pop();

        vis[x][y]--;

        for(int i=0; i<26; i++)
        {
            for(auto u:g[x][i])
            {
                for(auto v:g[y][i])
                {
                    if(d[u][v]>d[x][y]+1)
                    {
                        d[u][v]=d[x][y]+1;
                        if(vis[u][v]==0) q.push({u, v}), vis[u][v]++;
                    }
                }
            }
        }
    }
}

int main()
{
    FasterIO;

//    int tc; cin>>tc;
//    while(tc--)
    {
        int n, m; cin>>n>>m;
        for(int i=1; i<=m; i++)
        {
            int x, y; char c; cin>>x>>y>>c; ad[x][y]=ad[y][x]=1;
            g[x][c-'a'].push_back(y), g[y][c-'a'].push_back(x);
        }

        bfs(n);

        int mx=1e9;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(i==j) mx=min(mx, 2*d[i][j]);
                else
                {
                    if(ad[i][j]) mx=min(mx, 2*d[i][j]+1);
                }
            }
        }

        if(mx<1e9) cout<<mx<<endl;
        else       cout<<-1<<endl;
    }
    return 0;
}
