#include <bits/stdc++.h>
using namespace std;

const int maxn = 2010;
const int maxe = 10010;

int n, m, k = 2;
vector<vector<pair<int, int>>> G;
vector<vector<int>> dis[2], pre[2];
vector<bool> vis;
const int INF = 0x3f3f3f3f;

void InitializeSingleSource(int s) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            dis[j][s][i] = INF;
            pre[j][s][i] = 0;
        }
    }
    dis[0][s][s] = 0;
}

// DAG单源最短/次短路径
void DAG_TOP2_ShortestPath(int s, const vector<int>& topoList) {
    InitializeSingleSource(s);  // 初始化dis和pre
    // 按照拓扑序进行松弛
    for (int u : topoList) {
        for (auto [v, w] : G[u]) {
            if (dis[0][s][v] > dis[0][s][u] + w) {  // 松弛
                // 更新次短路
                dis[1][s][v] = dis[0][s][v];
                pre[1][s][v] = pre[0][s][v];
                // 更新最短路
                dis[0][s][v] = dis[0][s][u] + w;
                pre[0][s][v] = u;
            } else if (dis[1][s][v] > dis[0][s][u] + w) {  // 次短路
                dis[1][s][v] = dis[0][s][u] + w;
                pre[1][s][v] = u;
                // dis[0][s][u] + w <= dis[1][s][u] + w
            }
        }
    }
}
/*
// DAG单源TopK短路
void DAG_TOPK_ShortestPath(int s, const vector<int>& topoList){
        InitializeSingleSource(s); // 初始化dis和prev
        // 按照拓扑序进行松弛
        for (int u: topoList){
                for (auto [v, w]: G[u]){
                        int key = dis[0][s][u] + w;
                        int i;
                        // 将key插入至dis[0][s][v], ..., dis[k-1][s][v]的递增序列中
                        for (i=k-1; i>=0 && dis[i][s][v]>key; --i){
                                if(i<k-1){ // 后移覆盖
                                        dis[i+1][s][v] = dis[i][s][v];
                                        pre[i+1][s][v] = pre[i][s][v];
                                }
                        }
                        if(i<k-1){ // 插入key
                                dis[i+1][s][v] = key;
                                pre[i+1][s][v] = u;
                        }
                }
        }
}*/

// 获得从u出发所有可达顶点构成的诱导子图G'的顶点逆拓扑序列
void dfs(int u, vector<int>& path) {
    for (auto [v, _] : G[u]) {  // 访问u的相邻顶点v
        if (vis[v])
            continue;
        dfs(v, path);
        vis[v] = true;
    }
    path.push_back(u);  // 顶点完成访问时加入序列
}

void DAG_APSP() {
    dis[0] = dis[1] = vector<vector<int>>(n + 1, vector<int>(n + 1, INF));
    pre[0] = pre[1] = vector<vector<int>>(n + 1, vector<int>(n + 1));
    vis = vector<bool>(n + 1, false);
    vector<int> topo_order_list;  // 拓扑序列
    dfs(1, topo_order_list);      // 求得1和可达顶点的诱导子图拓扑序
    // for (auto x: topo_order_list) cout << x << "->";
    // cout << endl;
    reverse(topo_order_list.begin(),
            topo_order_list.end());  // 序列反转
    for (int s = 1; s <= n; ++s) {
        DAG_TOP2_ShortestPath(s, topo_order_list);
    }
}

// [s, ..., v]
vector<int> getPath(int k, int s, int v) {
    vector<int> ret;
    int cur = pre[k][s][v];
    ret.emplace_back(v);
    while (cur) {
        ret.emplace_back(cur);
        cur = pre[k][s][cur];
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

void printUnionPath(int x, int y) {
    auto path = getPath(0, 1, x);
    for (auto u : path) printf("%d->", u);
    printf("\n==========================\n");
    path = getPath(0, x, y);
    for (auto u : path) printf("%d->", u);
    printf("\n==========================\n");
    path = getPath(1, x, y);
    for (auto u : path) printf("%d->", u);
    printf("\n==========================\n");
    path = getPath(0, y, n);
    for (auto u : path) printf("%d->", u);
    printf("\n");
}

int main() {
    // INPUTS
    scanf("%d%d", &n, &m);
    G = vector<vector<pair<int, int>>>(n + 1);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({ v, w });
    }

    // 预处理全源Top2短路
    DAG_APSP();
    long long res = INF;
    int bestX, bestY;
    // 枚举x,y in [1, n] and x!=y
    for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= n; ++y) {
            if (x != y) {
                long long cur = 1LL * dis[0][1][x] + dis[0][y][n] + dis[0][x][y] + dis[1][x][y];
                if (cur < res) {
                    res = cur;
                    bestX = x, bestY = y;
                }
            }
        }
    }
    // printUnionPath(bestX, bestY); // 打印最优路径并
    printf("%lld\n", res);
    // auto path = getPath(1, 1, 4);
    // for (auto u: path) printf("%d->", u);
    return 0;
}