#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long LL;
const int INF = 0x3f3f3f3f;

const int maxn = 2e3 + 10;
const int maxm = 1e4 + 10;
struct Edge {
    int b, nt, w;
} E[maxm];
int ecnt, head[maxn];
void add_edge(int u, int v, int w) {
    E[++ecnt].b = v;
    E[ecnt].w = w;
    E[ecnt].nt = head[u];
    head[u] = ecnt;
}
struct Dis {
    int d1 = INF, d2 = INF;
    void update(Dis rhs) {
        update(rhs.d1);
        update(rhs.d2);
    }
    void update(int d) {
        if (d == INF)
            return;
        if (d < d1)
            d2 = d1, d1 = d;
        else if (d < d2)
            d2 = d;
    }
    Dis operator+(const int w) const { return (Dis){ d1 + w, d2 + w }; }
} dis[maxn][maxn];

int in[maxn], n, m;
bool vis[maxn];
void getin(int u) {
    vis[u] = 1;
    for (int e = head[u]; e; e = E[e].nt) {
        int v = E[e].b;
        in[v]++;
        if (vis[v])
            continue;
        getin(v);
    }
}
queue<int> q;
void getdis(int st, Dis dis[maxn]) {
    memset(in, 0, sizeof(in));
    memset(vis, 0, sizeof(vis));
    getin(st);
    while (!q.empty()) q.pop();
    q.push(st);
    dis[st] = (Dis){ 0, INF };
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = head[u]; e; e = E[e].nt) {
            int v = E[e].b, w = E[e].w;
            if (--in[v] == 0)
                q.push(v);
            dis[v].update(dis[u] + w);
        }
    }
}

void solve() {
    scanf("%d%d", &n, &m);
    rep(i, m) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    for (int i = 1; i <= n; i++) getdis(i, dis[i]);
    int ans = INF;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++)
            if (dis[u][v].d1 != INF && dis[u][v].d2 != INF)
                ans = min(ans, dis[1][u].d1 + dis[u][v].d1 + dis[u][v].d2 + dis[v][n].d1);
    printf("%d\n", ans);
}

int main() {
    solve();
    return 0;
}

/sandbox/1/a.cpp: In member function 'Dis Dis::operator+(int) const':
/sandbox/1/a.cpp:29:65: error: no matching function for call to 'Dis::Dis(<brace-enclosed initializer list>)'
     Dis operator + (const int w) const { return (Dis){d1+w, d2+w}; }
                                                                 ^
/sandbox/1/a.cpp:29:65: note: candidates are:
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis()
 struct Dis {
        ^
/sandbox/1/a.cpp:21:8: note:   candidate expects 0 arguments, 2 provided
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis(const Dis&)
/sandbox/1/a.cpp:21:8: note:   candidate expects 1 argument, 2 provided
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis(Dis&&)
/sandbox/1/a.cpp:21:8: note:   candidate expects 1 argument, 2 provided
/sandbox/1/a.cpp: In function 'void getdis(int, Dis*)':
/sandbox/1/a.cpp:48:39: error: no matching function for call to 'Dis::Dis(<brace-enclosed initializer list>)'
     q.push(st); dis[st] = (Dis){0, INF};
                                       ^
/sandbox/1/a.cpp:48:39: note: candidates are:
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis()
 struct Dis {
        ^
/sandbox/1/a.cpp:21:8: note:   candidate expects 0 arguments, 2 provided
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis(const Dis&)
/sandbox/1/a.cpp:21:8: note:   candidate expects 1 argument, 2 provided
/sandbox/1/a.cpp:21:8: note: constexpr Dis::Dis(Dis&&)
/sandbox/1/a.cpp:21:8: note:   candidate expects 1 argument, 2 provided
/sandbox/1/a.cpp: In function 'void solve()':
/sandbox/1/a.cpp:60:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
/sandbox/1/a.cpp:61:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     rep(i, m) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); }
                                                         ^