#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>


void solve() {
    int n, m;
    cin >> n >> m;

    // vector<vector<int>> e(n + 1, vector<int>());
    vector e(n + 1, vector<pii>());
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }

    const int inf = 1e9 + 10;
    vector<int> visi(n + 1), d(n + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    d[1] = 0;
    q.push({0, 1});

    while (q.size()) {
        auto [dis, u] = q.top(); q.pop();
        if (visi[u]) continue;
        visi[u] = 1;
        for (auto [v, w] : e[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }

    cout << (d[n] == inf ? -1 : d[n]) << '\n';
}
signed main() {
    int t = 1;
    // cin >> t;
    while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/