#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); }