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

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define f first
#define s second
#define nl "\n"
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MOD = 1e9+7;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

int n, m;
vector<pii> edges[26];
bool e[1000][1000];
vi adj[1000*999+999];
int dist[1000*999+999];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);

  cin >> n >> m;
  rep(i, 1, m){
    int u, v; char c;
    cin >> u >> v >> c;
    u--; v--;
    edges[c-'a'].pb({u, v});
    edges[c-'a'].pb({v, u});
    e[u][v]=e[v][u]=true;
  }

  rep(c, 0, 25){
    rep(i, 0, sz(edges[c])-1){
      rep(j, i+1, sz(edges[c])-1){
        int a=edges[c][i].f;
        int b=edges[c][i].s;
        int C=edges[c][j].f;
        int d=edges[c][j].s;
        adj[1000*min(a, C)+max(a, C)].pb(1000*min(b, d)+max(b, d));
      }
    }
  }

  //shortest dist from 1000*1+n to 1000a+a or 1000a+b (a-b)
  pqg<pii> pq;
  int ans=1e9;
  pq.push({0, n-1});
  while(!pq.empty()){
    pii p=pq.top(); pq.pop();
    int d=p.f;
    int u=p.s/1000;
    int v=p.s%1000;
    if(dist[p.s]) continue;
    dist[p.s]=d;
    if(u==v){
      ans=min(ans, 2*d); 
    }
    if(e[u][v]){
      ans=min(ans, 2*d+1); 
    }
    trav(k, adj[p.s]){
      if(dist[k]==0) pq.push({d+1, k});
    }
  }
  cout << (ans==1e9?-1:ans);
}
#include<bits/stdc++.h>
#define ll long long
#define N 2005
using namespace std;
struct node{
	int to,nxt;
}e[N*N*2];
int head[N],tot,d[N];
void build(int a,int b)
{
	++d[a],++d[b];
	e[++tot].to=b;
	e[tot].nxt=head[a];
	head[a]=tot;
	e[++tot].to=a;
	e[tot].nxt=head[b];
	head[b]=tot;
}
int n,m,vis[N];
char mp[N][N];
void dfs(int p)
{
	vis[p]=1;
	for(int i=head[p];i;i=e[i].nxt)
	{
		if(!vis[e[i].to])
		dfs(e[i].to);
	}
}
int main()
{
#ifdef lovelyG
Sfile(1);
#endif
	scanf("%d%d",&n,&m);
	build(1,1+n);
	build(1,m+n);
	build(n,1+n);
	build(n,m+n);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",mp[i]+1);
		for(int j=1;j<=m;++j)
		{
			if(mp[i][j]=='#')
			build(i,j+n);
		}
	}
	int numr=0,numc=0;
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])
		{
			++numr;
			if(d[i])++numc;
			dfs(i);
		}
	}
	for(int i=1;i<=m;++i)
	{
		if(!vis[i+n])
		{
			++numc;
		}
	}
	printf("%d",min(numr,numc)-1);
	return 0;
}