#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T>
struct edge {
    int src,to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost) : src(-1), to(to), cost(cost), id(-1) {}
    edge(int src, int to, T cost) : src(src), to(to), cost(cost), id(-1) {}
    edge(int src, int to, T cost, int id) : src(src), to(to), cost(cost), id(id) {}
    bool operator<(const edge &e) const {return cost < e.cost;}
};

template<typename T>
vector<T> Dijkstra(vector<vector<edge<T>>> &G, int s, T inf) {
    vector<T> dist(G.size(),inf);

    using Pi = pair<T, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> pq;
    dist[s] = 0;
    pq.emplace(dist[s],s);
    while (!pq.empty()) {
        T d; int v;
        tie(d,v) = pq.top(); pq.pop();
        if (d > dist[v]) continue;
        for (auto &e : G[v]) {
            if (dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                pq.emplace(dist[e.to],e.to);
            }
        }
    }

    return dist;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    int sz = 1;
    while (sz < N) sz <<= 1;
    vector<vector<edge<ll>>> G(N+sz*4+M*2);
    int in = N;
    int out = N+sz*2;
    int E = N+sz*4;
    rep(i,N) {
        G[in+i+sz].emplace_back(i,0);
        G[i].emplace_back(out+i+sz,0);
    }
    for (int i = 1; i < sz; i++) {
        G[in+i].emplace_back(in+(i<<1|0),0);
        G[in+i].emplace_back(in+(i<<1|1),0);
        G[out+(i<<1|0)].emplace_back(out+i,0);
        G[out+(i<<1|1)].emplace_back(out+i,0);
    }

    auto addedge=[&](auto&&self, int a, int b, int k, int l, int r, int v, int flag)->void {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            if (flag) {
                G[v].emplace_back(k+in,0);
            } else {
                G[k+out].emplace_back(v,0);
            }
            return;
        }

        self(self,a,b,k<<1|0,l,(l+r)>>1,v,flag);
        self(self,a,b,k<<1|1,(l+r)>>1,r,v,flag);
    };
    rep(i,M) {
        int u,v,w; cin >> u >> v >> w;
        --u;
        int Ein = E+i*2;
        int Eout = E+i*2+1;
        G[Eout].emplace_back(Ein,w);
        addedge(addedge,u,v,1,0,sz,Ein,1);
        addedge(addedge,u,v,1,0,sz,Eout,0);
    }

    auto dist = Dijkstra<ll>(G,0,1e18);

    cout << (dist[N-1]==1e18 ? -1 : dist[N-1]) << ln;
}



Measured memory_bytes: 144844