#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<i##end;i++)
#define REP(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define RFOR(i,a,b) for(int i=(a),i##end=(b);i>i##end;i--)
#define RREP(i,a,b) for(int i=(a),i##end=(b);i>=i##end;i--)
typedef long long LL;

const int maxs=(1<<16)+1;
const int maxn=9;
int dp[maxn][maxs],h,w,a,b,S;
inline int lowbit(const int& ans) {
	FOR(w,0,32) if(!(ans&(1<<w))) return w;
}
inline int right(const int& u,const int& st) {
	if(u%w==w-1) return -1;
	if(st&(1 << u+1)) return -1;
	return st|(1 << u+1)|(1<<u);
}
inline int down(const int& u,const int& st) {
	if(u+w>=S) return -1;
	if(st&(1 << u+w)) return -1;
	return st|(1 << u+w)|(1<<u);
}

int main() {
	memset(dp,0,sizeof(dp));
	scanf("%d%d%d%d",&h,&w,&a,&b);
	dp[a][0]=1;
	S=h*w;
	FOR(st,0,1<<S) REP(i,0,a) {
		int& ans=dp[i][st];
		if(!ans) continue;
		//printf("i=%d st=%d\n",i,st);
		int u=lowbit(st);
		if(u>=S) continue;
		dp[i][st|(1<<u)]+=ans;
		if(!i) continue;
		int r=right(u,st),d=down(u,st);
		if(r>=0) dp[i-1][r]+=ans;
		if(d>=0) dp[i-1][d]+=ans;
	}
	printf("%d\n",dp[0][(1<<S)-1]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using P=pair<int,int>;
using T=tuple<int,int,int>;
constexpr int mod=998244353;
constexpr LL inf=1e9;
constexpr double eps=1e-13;
constexpr double pi=3.141592653589;
int in(){
    int x;
    scanf("%d",&x);
    return x;
}
struct graph{
    vector<vector<vector<int>>>e;
    vector<vector<int>>dist;
    graph(int n){
        e.resize(n,vector<vector<int>>(26));
        dist.assign(n,vector<int>(n,inf));
    }
    void add_edge(int v,int u,int c){
        e[v][c].emplace_back(u);
        e[u][c].emplace_back(v);
    }
    void bfs(int s1,int s2){
        dist[s1][s2]=0;
        queue<P>q;
        q.push({s1,s2});
        while(q.size()){
            auto [v1,v2]=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                for(int j=0;j<e[v1][i].size();j++){
                    for(int k=0;k<e[v2][i].size();k++){
                        int u1=e[v1][i][j],u2=e[v2][i][k];
                        if(dist[v1][v2]+1<dist[u1][u2]){
                            dist[u1][u2]=dist[v1][v2]+1;
                            q.push({u1,u2});
                        }
                    }
                }
            }
        }
    }
};
int main(){
    int n=in(),m=in();
    graph g(n);
    int a[m],b[m];
    for(int i=0;i<m;i++){
        a[i]=in()-1,b[i]=in()-1;
        char c;
        cin>>c;
        g.add_edge(a[i],b[i],c-'a');
    }
    g.bfs(0,n-1);
    int ans=inf;
    for(int i=0;i<n;i++)ans=min(ans,g.dist[i][i]*2);
    for(int i=0;i<m;i++)ans=min(ans,min(g.dist[a[i]][b[i]],g.dist[b[i]][a[i]])*2+1);
    cout<<(ans<inf ? ans : -1)<<endl;
    return 0;
}