考虑边拆成点。然后经过这些点的路径就是答案的路径。
考虑直接起点，终点连边。
然后我们考虑转移两条出边入边的过程。是 \((a, b) \to (b, c)\) 考虑到反向边是一致的所以可以 \((b, a) \to (b, c)\)。这个启发我们反向边之间可以连一条 \(w\) 的边。
然后我们考虑按 w 排序，然后 \(i \to i + 1\) 连一个差值，\(i + 1 \to i\) 连一个 0 边就做完了。
我们发现取我们可以在一个点中不断转移差值，这个就是取 max 的过程，然后通过反向边走出去，这个建图真的牛子的。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define pb push_back
#define lc u << 1
#define rc u << 1 | 1
#define int long long
using namespace std;
const int _ = 1e5 + 5, __ = 2e5 + 5, mod = 1e9 + 7;
int n, m, dis[__], s = 0, t = 1;
struct EDGE {
int v, w, id;
bool operator < (const EDGE & x) const { return w < x.w; }
} ;
vector <EDGE> e[_], g[_];
void adde (int u, int v, int w, int id) { e[u].pb({v, w, id}); }
void addg (int u, int v, int w) { g[u].pb({v, w, 114514}); }
struct node {
int u, d;
bool operator < (const node & x) const { return d > x.d; }
} ;
priority_queue <node> q;
void dijkstra (int st, int ed) {
memset(dis, 0x3f, sizeof(dis)), dis[st] = 0;
q.push({st, 0});
while (! q.empty()) {
int u = q.top().u, d = q.top().d;
q.pop(); if (d != dis[u]) continue ;
for (auto & [v, w, id] : g[u])
if (dis[v] > d + w) dis[v] = d + w, q.push({v, dis[v]});
}
cout << dis[ed]; return ;
}
signed main () {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios :: sync_with_stdio(0);
cin >> n >> m;
rep(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
adde(u, v, w, i << 1), adde(v, u, w, i << 1 | 1);
}
rep(u, 1, n) {
if (e[u].empty()) continue ;
sort(e[u].begin(), e[u].end());
for (auto & [v, w, id] : e[u]) {
addg(id, id ^ 1, w);
if (u == 1) addg(s, id, w);
if (v == n) addg(id, t, w);
}
auto it = e[u].begin();
for (++ it; it != e[u].end(); it ++) {
auto prv = (it - 1);
addg(it -> id, prv -> id, 0), addg(prv -> id, it -> id, it -> w - prv -> w);
}
}
dijkstra(s, t);
return 0;
}