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

int dist[1005][1005];
int A[1005],B[1005];
char C[1005];
vector<pair<int,int> > G[1005];

main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N,M;
	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>A[i]>>B[i]>>C[i];
		G[A[i]].push_back(make_pair(B[i],C[i]));
		G[B[i]].push_back(make_pair(A[i],C[i]));
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) dist[i][j] = (1 << 29);
	}
	queue<pair<int,int > > Q;
	dist[1][N]=0;
	Q.emplace(1,N);
	while(Q.size()){
		auto [pos1,pos2]=Q.front();
		Q.pop();
		for(pair<int,int> e1:G[pos1]){
			for(pair<int,int> e2:G[pos2]){
				if(e1.second!=e2.second)continue;
				if(dist[e1.first][e2.first]==(1<<29)){
					dist[e1.first][e2.first]=dist[pos1][pos2]+1;
					Q.emplace(e1.first,e2.first);
				}
			}
		}
	}
	int ans=(1<<29);
	for(int i=1;i<=N;i++){
		ans=min(ans,2*dist[i][i]);
	}
	for(int i=0;i<M;i++){
		ans=min(ans,2*dist[A[i]][B[i]]+1);
		ans=min(ans,2*dist[B[i]][A[i]]+1);
	}
	if(ans!=(1<<29))cout<<ans<<endl;
	else cout<<-1<<endl;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
#define d rd()
ll a,b,k,aa,bb;
ll yh[65][65];
ll now,ans;
int main(){
	a=aa=d,b=bb=d,k=d;
	yh[0][0]=1,yh[1][0]=yh[1][1]=1;
	f(i,2,61){
		yh[i][0]=yh[i][i]=1;
		f(j,1,i-1)yh[i][j]=yh[i-1][j]+yh[i-1][j-1];
	}
	f(i,1,a+b){
		if(!aa)bb--,cout<<"b";
		else if(!bb)cout<<"a",aa--;
		else if(now+yh[aa+bb-1][aa-1]<k)now+=yh[aa+bb-1][aa-1],bb--,cout<<"b";
		else cout<<"a",aa--;
	}
	return 0;
}
