#include <bits/stdc++.h>
using namespace std;
const int N = 1020, M = 10020;
struct Edge {
    int ver, val, Next;
} e[M];
int n, m, t, Head[N], deg[N], f[N], g[N];
queue<int> Q;
vector<pair<int, int>> T[N];
inline void Insert(int x, int y, int v) { e[++t] = { y, v, Head[x] }, Head[x] = t; }
int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        Insert(x, y, v), deg[y]++;
    }
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    Q.push(1), f[1] = 0;
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        sort(T[x].begin(), T[x].end());
        if (T[x].size() >= 2) {
            g[x] = min(g[x], T[x][0].first + T[x][1].first);
        }
        for (int i = Head[x]; i; i = e[i].Next) {
            int y = e[i].ver;
            deg[y]--;
            if (!deg[y])
                Q.push(y);
            f[y] = min(f[y], f[x] + e[i].val);
            g[y] = min(g[y], g[x] + e[i].val);
            T[y].push_back({ f[x] + e[i].val, x });
        }
    }
    return printf("%d\n", g[n]), 0;
}

/sandbox/1/a.cpp:6:34: error: '>>' should be '> >' within a nested template argument list
    6 | queue<int> Q; vector<pair<int,int>> T[N];
      |                                  ^~
      |                                  > >
/sandbox/1/a.cpp: In function 'void Insert(int, int, int)':
/sandbox/1/a.cpp:7:62: warning: extended initializer lists only available with '-std=c++11' or '-std=gnu++11'
    7 | inline void Insert(int x,int y,int v) { e[++t] = {y,v,Head[x]}, Head[x] = t; }
      |                                                              ^
/sandbox/1/a.cpp:7:62: warning: extended initializer lists only available with '-std=c++11' or '-std=gnu++11'
/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:29:28: warning: extended initializer lists only available with '-std=c++11' or '-std=gnu++11'
   29 |             T[y].push_back({f[x]+e[i].val, x});
      |                            ^
/sandbox/1/a.cpp:29:46: warning: extended initializer lists only available with '-std=c++11' or '-std=gnu++11'
   29 |             T[y].push_back({f[x]+e[i].val, x});
      |                                              ^
/sandbox/1/a.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
/sandbox/1/a.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d%d%d", &x, &y, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~