#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
template<class in_chmax> void chmax(in_chmax &x, in_chmax y) {x = max(x,y);}
template<class in_chmin> void chmin(in_chmin &x, in_chmin y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll maxN = 1100;

ll N, M;
bool con[maxN][maxN];
map<char,vector<pair<ll,ll>>> Mp;
vector<ll> G[maxN*maxN];

ll id(pair<ll,ll> p) {return p.first*N + p.second;}
ll id(ll i, ll j) {return id({i,j});}

vector<ll> bfs(ll st) {
    vector<ll> dist(N*N,inf);
    dist[st] = 0;
    queue<ll> que;
    que.push(st);
    while (que.size()) {
        ll now = que.front();
        que.pop();
        ll i = now/N, j = now%N;
        for (ll to : G[now]) {
            if (dist[to]!=inf) continue;
            dist[to] = dist[now]+2;
            que.push(to);
        }
    }
    return dist;
}

int main() {
    cin >> N >> M;
    rep(i,M) {
        ll a, b; char c;
        cin >> a >> b >> c;
        a--; b--;
        Mp[c].push_back({a,b});
        Mp[c].push_back({b,a});
        con[a][b] = con[b][a] = true;
    }
    for (auto p : Mp) {
        vector<pair<ll,ll>> vec = p.second;
        for (pair<ll,ll> s : vec) {
            for (pair<ll,ll> t : vec) {
                pair<ll,ll> from = {s.first,t.first};
                pair<ll,ll> to = {s.second,t.second};
                G[id(from)].push_back(id(to));
                G[id(to)].push_back(id(from));
            }
        }
    }
    vector<ll> dist = bfs(id(0,N-1));
    ll ans = inf;
    rep(id,N*N) {
        ll i = id/N, j = id%N;
        if (i==j) chmin(ans,dist[id]);
        else if (con[i][j]) chmin(ans,dist[id]+1);
    }
    if (ans==inf) ans = -1;
    Cout(ans);
}
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define RREP_(i, a_, b_, a, b, ...) for (Int i = Int(b) - 1, low##i = (a); i >= low##i; i--)
#define RREP(i, ...) RREP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on
struct in {
    template <class T> operator T() {
        T t;
        std::cin >> t;
        return t;
    }
};
void out() { std::cout << "\n"; }
template <class Head, class... Tail> void out(Head&& h, Tail&&... t) {
    std::cout << h << (sizeof...(Tail) == 0 ? "" : " "), out(std::forward<Tail>(t)...);
}
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }

/**
 *    author:  knshnb
 *    created: Thu Nov 19 18:45:12 JST 2020
 **/

signed main() {
    Int n = in(), X = in();
    std::vector<Int> a(n), b(n - 1);
    REP(i, n) a[i] = in();
    REP(i, n - 1) b[i] = a[i + 1] / a[i];
    std::vector<Int> use(n);
    RREP(i, n) {
        use[i] = X / a[i];
        X %= a[i];
    }
    std::vector<std::map<Int, Int>> dp(n);
    dp[0][use[0]] = 1;
    REP(i, n - 1) {
        for (auto& p : dp[i]) {
            if (p.first != b[i]) dp[i + 1][use[i + 1]] += p.second;
            if (p.first != 0) dp[i + 1][use[i + 1] + 1] += p.second;
        }
    }
    Int ans = 0;
    for (auto& p : dp.back()) ans += p.second;
    out(ans);
}
