#include <bits/stdc++.h> using namespace std; const int maxn = 1010; const int maxe = 10010; int head[maxn]; int cnt = 0; struct info { int to, w, nxt; } e[maxe]; void add(int u, int v, int w) { ++cnt; e[cnt] = { v, w, head[u] }; head[u] = cnt; } const int INF = 0x3f3f3f3f; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; add(u, v, w); } // 预处理任意两点的最短路和次短路 vector<vector<int>> fir(n + 1, vector<int>(n + 1, INF)), sec(n + 1, vector<int>(n + 1, INF)); function<void(int)> topoSort = [&](int u) -> void { // 维护u的遍历子图的入度 vector<int> inDeg(n + 1, 0); queue<int> que; que.push(u); while (!que.empty()) { auto x = que.front(); que.pop(); for (int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; inDeg[y]++; que.push(y); } } // 从u出发的拓扑排序 que.push(u); fir[u][u] = 0; while (!que.empty()) { auto x = que.front(); que.pop(); for (int i = head[x]; i; i = e[i].nxt) { int y = e[i].to, w = e[i].w; if (fir[u][y] >= fir[u][x] + w) { sec[u][y] = fir[u][y]; fir[u][y] = fir[u][x] + w; } else if (sec[u][y] > fir[u][x] + w) { sec[u][y] = fir[u][x] + w; } if (--inDeg[y] == 0) { que.push(y); } } } }; for (int u = 1; u <= n; ++u) { topoSort(u); } // 1-x x-y y-n int ans = INF; for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { if (sec[x][y] != INF) { // x->y存在两条路径 ans = min(1LL * ans, 1LL * fir[1][x] + fir[y][n] + fir[x][y] + sec[x][y]); } } } cout << ans << endl; return 0; }