#include <bits/stdc++.h>
#define LL long long
#define st first
#define nd second

const LL LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
using namespace std;

template <class T> T read(T &a) {
    a=0;char x=getchar();bool f=0;
    for(;x<'0'||x>'9';x=getchar())f|=x=='-';
	for(;x>='0'&&x<='9';x=getchar())a=(a<<3)+(a<<1)+x-'0';
    if(f)a=-a;
    return a;
}
template <class T> void write(T a) {
    static char s[40];int len=-1;
    if(a<0)putchar('-'),a=-a;
    if(a==0)putchar('0');
    for (int i=0;i<40;++i)s[i]=0;
    for(;a!=0;s[++len]=a%10+'0',a/=10);
    for(int i=len;i>=0;--i)putchar(s[i]);
}
template <class T> void writeln(T a) {
    write(a);
    puts("");
}

int n, k;

int main() {
    read(n), read(k);
    if (n == 1 && k == 0) {
        puts("1 2");
        return 0;
    }
    if (k < 0 || k > n - 2) {
        puts("-1");
        return 0;
    }
    printf("%d %d\n", 1, (k + 2) * 2);
    for (int i = 1; i <= k + 1; ++i) {
        printf("%d %d\n", i * 2, i * 2 + 1);
    }
    for (int i = k + 3; i <= n; ++i) {
        printf("%d %d\n", i * 2, i * 2 + 1);
    }
    return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define SZ(x) (int)x.size()
#define pb push_back
#define FULL(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N = 1000005, M = 1005;
int n, m;
vector<int> c[26], g[N];
int f[M][M], vis[N], dis[N];

void add(int a, int b, int u, int v) {
	int x = a*n + u, y = b*n + v;
	g[x].pb(y), g[y].pb(x);
	x = b*n + u, y = a*n + v;
	g[x].pb(y), g[y].pb(x);
	x = b*n + v, y = a*n + u;
	g[x].pb(y), g[y].pb(x);
	x = a*n + v, y = b*n + u;
	g[x].pb(y), g[y].pb(x);
}

int main() {
	cin>> n >> m;
	int a, b, u, v;
	char ch;
	for(int i=1; i<=m; ++i) {
		cin>> a >> b >> ch;
		u = a - 1, v = b - 1;
		f[u][v] = 1, f[v][u] =1;
		c[ch-'a'].pb(u*n+v);
	}
	for(int i=0; i<26; ++i) {
		int len = SZ(c[i]);
		for(int j=0; j<len; ++j) {
			for(int k=j+1; k<len; ++k) {
				a = c[i][j]/n, b = c[i][j] - a*n;
				u = c[i][k]/n, v = c[i][k] - u*n;
				add(a, b, u, v), add(u, v, a, b);
			}
		} 
	}
	queue<int> q;
	q.push(n-1);
	vis[n-1] = 1;
	dis[n-1] = 0;
	while(!q.empty()) {
		int fr = q.front();
		q.pop();
		for(int i=0; i<SZ(g[fr]); ++i) {
			v = g[fr][i];
			if (!vis[v]) {
				dis[v] = dis[fr] + 1;
				vis[v] = 1;
				q.push(v);
			}
		}
	}
	int ans = -1;
	for(int i=0; i<n; ++i) {
		v = i*n + i;
		if (vis[v] && (ans == -1 || (dis[v]*2 < ans))) {
			ans = dis[v] * 2;
		} 
	}
	for(int i=0; i<n ;++i) {
		for(int j=0; j<n; ++j) {
			v = i*n + j; 
			if (f[i][j] && vis[v] && (ans == -1 || (dis[v]*2 + 1 < ans))) {
				ans = dis[v]*2 + 1;
			}
		}
	}
	cout<< ans << endl;
	return 0;
}