#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>
#include<map>
#include<cassert>

using namespace std;

#define ll long long
#define reps(i, a, b) for(int i = a; i < b; i++)
#define rreps(i, a, b) for(int i = a-1; i >= b; i--)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) rreps(i, n, 0)
#define P pair<int, int>
#define vec vector<int>
#define mat vector<vec>

const ll mod = 1000000007;
const int INF = 1001001001;

int n, m;

int node(int x, int y) {
    return x * n + y;
}

P node_inv(int u){
    return P(u/n, u%n);
}

struct edge {
    int u, v;
    char c;
    edge(int u_, int v_, char c_){
        u = u_; v = v_; c = c_;
    }
};

int main(){
    cin >> n >> m;
    vector<edge> e;
    rep(i, m){
        int a, b;
        char c;
        cin >> a >> b >> c;
        a--; b--;
        e.push_back(edge(a, b, c));
    }
    mat g(n*n);
    rep(i, e.size()){
        rep(j, e.size()){
            if(e[i].c == e[j].c){
                int u1 = node(e[i].u, e[j].u);
                int v1 = node(e[i].v, e[j].v);
                int u2 = node(e[i].u, e[j].v);
                int v2 = node(e[i].v, e[j].u);
                g[u1].push_back(v1);
                g[v1].push_back(u1);
                g[u2].push_back(v2);
                g[v2].push_back(u2);
                // cout << u1 << " " << v1 << " " << u2 << " " << v2 << endl;
            }
        }
    }

    // rep(i, n*n){
    //     P p = node_inv(i);
    //     cout << p.first << " " << p.second << endl;
    //     rep(j, g[i].size()){
    //         cout << g[i][j] << " ";
    //     }cout << endl;
    //     cout << endl;
    // }

    // 奇数距離
    queue<P> que;
    que.push(P(node(0, n-1), 0));
    vec dist(n*n, INF);
    dist[node(0, n-1)] = 0;
    int ans = INF;
    while(que.size() > 0){
        int u = que.front().first;
        int d = que.front().second;
        que.pop();
        rep(i, g[u].size()){
            int v = g[u][i];
            if(dist[v] <= d+1) continue;
            dist[v] = d+1;
            que.push(P(v, d+1));
            P p = node_inv(v);
            if(p.first == p.second){
                ans = min(ans, (d+1) * 2);
            }
        }
        // cout << node_inv(u).first+1 << " " << node_inv(u).second+1 << " " << d << endl;
    }

    // 偶数距離
    rep(i, e.size()){
        ans = min(ans, dist[node(e[i].u, e[i].v)]*2+1);
        ans = min(ans, dist[node(e[i].v, e[i].u)]*2+1);
    }

    if(ans == INF) ans = -1;
    cout << ans << endl;
}
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, ans;
  string s;
  cin >> N >> s;
  ans = N;
  
  auto itr = s.begin();
  while (distance(itr, s.end()) >= 3) {
    if (*itr=='f' && *(itr+1)=='o' && *(itr+2)=='x') {
      ans -= 3;
      s.erase(itr, itr+3);
      itr--; itr--;
    }
    else itr++;
  }
  cout << ans << endl;
}

  
      


      




