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

int n, m, a, b;
vector<pair<int, int> > ke[400009];
int d[400009][11];
bool marked[400009][11];

struct info {
    int d;
    int u;
    int w;
    info(int _d, int _u, int _w) : d(_d), u(_u), w(_w) {}

    bool operator()(const info x) {
        if (d < x.d) return true;
    }
};

struct infoComparator {
    bool operator()(const info& t1, const info& t2) {
        return t1.d > t2.d;
    }
};

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // cout << u << " " << v << " " << w << endl;
        ke[u].push_back({v + n, w});
        ke[v].push_back({u + n, w});
        ke[v + n].push_back({u, w});
        ke[u + n].push_back({v, w});
        d[u][w] = d[v][w] = d[v + n][w] = d[u + n][w] = INT_MAX;
    }

    priority_queue<info, vector<info>, infoComparator> pq;

    pq.push({0, 1, 0});
    int ans = INT_MAX;

    while (pq.size()) {
        auto top = pq.top();
        pq.pop();

        int u = top.u, w = top.w;

        if (marked[u][w]) continue;

        if (u == n) {
            ans = top.d;
            break;
        }

        marked[u][w] = true;

        for (auto& [v, _w] : ke[u]) {  // c(u,v) = w
            if (marked[v][_w]) continue;

            if (u <= n) {
                if (d[v][_w] >= top.d) {
                    d[v][_w] = top.d;
                    pq.push({top.d, v, _w});
                }
            } else {
                int cost = top.d + w * _w;
                if (cost < d[v][_w]) {
                    d[v][_w] = cost;
                    pq.push({cost, v, _w});
                }
            }
        }
    }

    cout << (ans < INT_MAX ? ans : -1) << endl;
}