#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
using namespace std;
int n, m, in[2005];
vector<vector<pair<int, int>>> tip;
vector<int> g;
vector<int> vis;
int dis[2005][2005][2];
void toposort() {
    int qn = 0;
    for (int i = 1; i <= n; ++i)
        if (!deg[i])
            q[++qn] = i;
    for (int i = 1; i <= qn; ++i) {
        int u = q[i];
        for (auto [v, w] : G[u])
            if (!--deg[v])
                q[++qn] = v;
    }
    assert(qn == n);
    for (int i = 1; i <= n; ++i) id[q[i]] = i;
}
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j][0] = 1e9;
            dis[i][j][1] = 1e9;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    tip.resize(n + 1);
    vis.resize(n + 1);
    g.push_back(0);
    int x, y, l;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &l);
        tip[x].push_back(mp(y, l));
        in[y]++;
    }
    toposort();
    init();
    for (int i = 1; i <= n; i++) {
        dis[i][i][0] = 0;
        for (int j = 1; j <= n; j++) {
            int u = g[j];
            if (dis[i][u][0] >= 1e9) {
                continue;
            }
            for (auto [a, b] : tip[u]) {
                int val = dis[i][u][0] + b;
                if (val < dis[i][a][0]) {
                    dis[i][a][1] = dis[i][a][0];
                    dis[i][a][0] = val;
                } else {
                    dis[i][a][1] = min(dis[i][a][1], val);
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = min(ans, dis[1][i][0] + dis[i][j][0] + dis[i][j][1] + dis[j][n][0]);
        }
    }
    printf("%d\n", ans);
}

/sandbox/1/a.cpp:14:14: error: use of undeclared identifier 'deg'; did you mean 'dec'?
        if (!deg[i])
             ^~~
             dec
/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/ios_base.h:1023:3: note: 'dec' declared here
  dec(ios_base& __base)
  ^
/sandbox/1/a.cpp:14:14: error: subscript of pointer to function type 'std::ios_base &(std::ios_base &)'
        if (!deg[i])
             ^~~
/sandbox/1/a.cpp:15:13: error: use of undeclared identifier 'q'
            q[++qn] = i;
            ^
/sandbox/1/a.cpp:17:17: error: use of undeclared identifier 'q'
        int u = q[i];
                ^
/sandbox/1/a.cpp:18:28: error: use of undeclared identifier 'G'
        for (auto [v, w] : G[u])
                           ^
/sandbox/1/a.cpp:18:19: warning: decomposition declarations are a C++17 extension [-Wc++17-extensions]
        for (auto [v, w] : G[u])
                  ^~~~~~
/sandbox/1/a.cpp:19:20: error: use of undeclared identifier 'deg'; did you mean 'dec'?
            if (!--deg[v])
                   ^~~
                   dec
/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/bits/ios_base.h:1023:3: note: 'dec' declared here
  dec(ios_base& __base)
  ^
/sandbox/1/a.cpp:20:17: error: use of undeclared identifier 'q'
                q[++qn] = v;
                ^
/sandbox/1/a.cpp:23:34: error: unknown type name 'id'; did you mean 'std::thread::id'?
    for (int i = 1; i <= n; ++i) id[q[i]] = i;
                                 ^~
                                 std::thread::id
/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/thread:88:11: note: 'std::thread::id' declared here
    class id
          ^
/sandbox/1/a.cpp:23:37: error: use of undeclared identifier 'q'
    for (int i = 1; i <= n; ++i) id[q[i]] = i;
                                    ^
/sandbox/1/a.cpp:23:43: error: expected unqualified-id
    for (int i = 1; i <= n; ++i) id[q[i]] = i;
                                          ^
/sandbox/1/a.cpp:53:22: warning: decomposition declarations are a C++17 extension [-Wc++17-extensions]
            for(auto [a,b]:tip[u]){
                     ^~~~~
2 warnings and 10 errors generated.