#include <fstream>
#include <queue>
#pragma warning(disable: 4996)

using namespace std;

typedef pair<uint32_t, uint32_t> edge;

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    uint32_t n;
    uint32_t m;
    scanf("%d %d", &n, &m);
    vector<vector<edge>> adj(n + 1);
    uint32_t u;
    uint32_t v;
    uint32_t w;
    uint32_t j;
    bool found;
    for (uint32_t i = 0; i < m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        found = false;
        if (u != v) {
            /*for (j = 0; j < adj[u].size(); ++j) {
                if (adj[u][j].first == v) { found = true; break; }
            }
            if (found && adj[u][j].second > w) { adj[u][j].second = w; }
            else { adj[u].push_back(edge(v, w)); }*/
            adj[u].push_back(edge(v, w));
        }
    }
    vector<uint64_t> paths(n + 1, INT_MAX);
    vector<bool> visited(n + 1);
    auto comp = [&paths](uint32_t a, uint32_t b) { return paths[b] < paths[a]; };
    priority_queue<uint32_t, vector<uint32_t>, decltype(comp)> q(comp, vector<uint32_t>(0));
    size_t size;
    q.push(1);
    paths[1] = 0;
    while (!q.empty()) {
        u = q.top();
        q.pop();
        if (!visited[u]) {
            visited[u] = true;
            size = adj[u].size();
            for (size_t i = 0; i < size; ++i) {
                paths[adj[u][i].first] = min(paths[u] + adj[u][i].second, paths[adj[u][i].first]);
                q.push(adj[u][i].first);
            }
        }
    }
    printf("%lld\n", paths[n]);
    return 0;
}