#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;
#define int long long
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define all(a) a.begin(), a.end()
#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define ii pair<int, int>
#define iii tuple<int, int, int>
#define vc vector
#define sz(a) a.size()
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)
#define setval(arr, x) memset(arr, x, sizeof(arr))
template<typename T>
using vv = vc<vc<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int INF = 4e18;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vc<int> a(m), b(m), c(m);
rep(i, 0, m) cin >> a[i] >> b[i] >> c[i];
vv<ii> incoming(n+1);
vv<int> oc(n+1);
rep(i, 0, m) {
incoming[b[i]].pb({a[i], c[i]});
oc[a[i]].pb(c[i]);
}
rep(u, 1, n+1) {
auto &vec = oc[u];
if (sz(vec)) sort(all(vec), greater<int>());
}
vc<int> dist(n+1, INF);
dist[n] = 0;
priority_queue<ii, vc<ii>, greater<ii>> pq;
pq.push({0, n});
vc<int> cp(n+1, 0);
while (sz(pq)) {
auto [d, v] = pq.top();
pq.pop();
if (d != dist[v]) continue;
for (auto &pr : incoming[v]) {
int u = pr.fr;
cp[u]++;
int idx = cp[u]-1;
if (idx < sz(oc[u])) {
int can = oc[u][idx] + dist[v];
if (can < dist[u]) {
dist[u] = can;
pq.push({dist[u], u});
}
}
}
}
cout << (dist[1] < INF/2 ? dist[1] : -1);
}
