#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept: itr(pos) { }
        constexpr void operator ++ () noexcept { ++itr; }
        constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator * () const noexcept { return itr; }
    };
    const Iter first, last;
public:
    explicit constexpr rep(const usize first, const usize last) noexcept: first(first), last(std::max(first, last)) { }
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T, T Div = 2>
constexpr T INFTY = std::numeric_limits<T>::max() / Div;

template <class T>
bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class F>
struct RecLambda: private F {
    explicit constexpr RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    constexpr decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class T>
using Vec = std::vector<T>;

void F_main() {
    usize N, M;
    std::cin >> N >> M;
    Vec<std::array<Vec<usize>, 26>> base(N);
    Vec<Vec<bool>> between(N, Vec<bool>(N));
    for (auto i: rep(0, M)) {
        usize u, v;
        char c;
        std::cin >> u >> v >> c;
        u -= 1;
        v -= 1;
        const usize k = c - 'a';
        base[u][k].push_back(v);
        base[v][k].push_back(u);
        between[u][v] = between[v][u] = true;
    }
    Vec<Vec<usize>> graph(N * N);
    for (auto u: rep(0, N)) {
        for (auto v: rep(0, N)) {
            for (const auto k: rep(0, 26)) {
                for (const auto x: base[u][k]) {
                    for (const auto y: base[v][k]) {
                        graph[x * N + y].push_back(u * N + v);
                    }
                }
            }
        }
    }
    Vec<usize> dist(N * N, INFTY<usize>);
    std::deque<usize> que;
    for (auto u: rep(0, N)) {
        for (auto v: rep(0, N)) {
            if (u == v) {
                setmin<usize>(dist[u * N + v], 0);
                que.push_front(u * N + v);
            }
            else if (between[u][v]) {
                setmin<usize>(dist[u * N + v], 1);
                que.push_back(u * N + v);
            }
        }
    }
    while (!que.empty()) {
        const auto u = que.front();
        que.pop_front();
        for (const auto v: graph[u]) {
            if (setmin(dist[v], dist[u] + 2)) {
                que.push_back(v);
            }
        }
    }
    const auto ans = dist[0 * N + (N - 1)];
    if (ans == INFTY<usize>) {
        std::cout << -1 << '\n';
    }
    else {
        std::cout << ans << '\n';
    }
    return;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    F_main();
    return 0;
}

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout << fixed << setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on

struct edge {
    int v;
    ll cost;
};
struct edg2 {
    int v;
    ll c;
    ll d;
};
class greater_cost {
   public:
    bool operator()(const edge& lh, const edge& rh) const {
        return lh.cost > rh.cost;
    }
};
using pq_mincost = priority_queue<edge, vector<edge>, greater_cost>;

const ll LG = 1e17;
vector<vector<edge>> edgcost;
vector<vector<edg2>> edgs;
vector<ll> c;
vector<ll> d;
ll dijkstra() {
    ll n = edgs.size();
    vector<bool> done(n, false);
    pq_mincost pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        ll cost = e.cost;
        int u = e.v;
        if (done[u]) continue;
        done[u] = true;

        if (u == n - 1) {
            return cost;
        }
        for (auto v : edgs[u]) {
            ll nc = cost + v.c + v.d / (cost + 1); // 即出発
            // t=sqrt(d)付近がよい
            ll left = sqrt(v.d) - 20;
            ll right = sqrt(v.d) + 20;
            for (ll t = left; t <= right; t++) {
                if(t < cost) continue;
                ll x = t + v.c + v.d / (t + 1);
                nc = min(x, nc);
            }
            pq.push({v.v, nc});
        }
    }
    return -1;
}
int main() {
    // ダイクストラで三分探索(!?)
    ioinit();
    ll n, m;
    cin >> n >> m;
    edgcost.resize(n);
    edgs.resize(n);
    c.resize(m);
    d.resize(m);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b >> c[i] >> d[i];
        a--;
        b--;
        edgs[a].push_back({int(b), c[i], d[i]});
        edgs[b].push_back({int(a), c[i], d[i]});
    }
    ll ans = dijkstra();
    print(ans);
}
