据 GPT6 研究，std 和数据（测试点 17～19）是错的。

GPT6 写的新 std：

// QOJ 443 / NOI 2020: Road Renovation
// C++17. Standard input / standard output.
// Reference: Xiao Mao, arXiv:2101.03519v3, Sections 3 and 6.
// This implementation uses iterative DFS, preserves parallel edges after
// contraction, and uses exact, deterministic shortest-path tie breaking.
#include <bits/stdc++.h>
using namespace std;

namespace road {
using i64 = long long;
constexpr i64 INF = (1LL << 62);

struct Edge { int u, v, w; };
struct Arc { int to, id; };
struct Graph {
    int n = 0;
    vector<Edge> e;
    vector<int> off;
    vector<Arc> a;
    Graph() = default;
    Graph(int n_, vector<Edge> es) : n(n_), e(move(es)), off(n + 1) {
        for (auto x : e) ++off[x.u + 1], ++off[x.v + 1];
        partial_sum(off.begin(), off.end(), off.begin());
        auto cur = off;
        a.resize(2 * e.size());
        for (int i = 0; i < (int)e.size(); ++i) {
            auto x = e[i];
            a[cur[x.u]++] = {x.v, i};
            a[cur[x.v]++] = {x.u, i};
        }
        for (int u = 0; u < n; ++u)
            sort(a.begin() + off[u], a.begin() + off[u + 1],
                 [](Arc x, Arc y) { return x.to < y.to; });
    }
    int edgeId(int u, int v) const {
        auto it = lower_bound(a.begin() + off[u], a.begin() + off[u + 1], v,
                              [](Arc x, int y) { return x.to < y; });
        return it != a.begin() + off[u + 1] && it->to == v ? it->id : -1;
    }
};

struct DSU {
    vector<int> p;
    explicit DSU(int n) : p(n, -1) {}
    int find(int x) {
        int r = x;
        while (p[r] >= 0) r = p[r];
        while (x != r) { int y = p[x]; p[x] = r; x = y; }
        return r;
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y]; p[y] = x;
    }
};

// Vertex-biconnected components of a possibly disconnected multigraph.
// eu/ev are indexed by ORIGINAL edge id. An endpoint of -1 means omitted.
// Self-loops are omitted; parallel edges are NOT combined.
struct Blocks {
    vector<int> id, begin, edges;
};
Blocks biconnected(int n, const vector<int>& eu, const vector<int>& ev) {
    int m = (int)eu.size();
    vector<int> off(n + 1);
    for (int i = 0; i < m; ++i)
        if (eu[i] >= 0 && eu[i] != ev[i])
            ++off[eu[i] + 1], ++off[ev[i] + 1];
    partial_sum(off.begin(), off.end(), off.begin());
    vector<Arc> adj(off[n]);
    auto cur = off;
    for (int i = 0; i < m; ++i) if (eu[i] >= 0 && eu[i] != ev[i]) {
        adj[cur[eu[i]]++] = {ev[i], i};
        adj[cur[ev[i]]++] = {eu[i], i};
    }
    vector<int> dfn(n), low(n), parent(n, -1), pe(n, -1), it = off;
    vector<int> stack, es;
    stack.reserve(n); es.reserve(m);
    Blocks out;
    out.id.assign(m, -1); out.begin.push_back(0); out.edges.reserve(m);
    int timer = 0;
    for (int root = 0; root < n; ++root) if (!dfn[root] && off[root] != off[root + 1]) {
        dfn[root] = low[root] = ++timer;
        stack.push_back(root);
        while (!stack.empty()) {
            int u = stack.back();
            if (it[u] < off[u + 1]) {
                Arc x = adj[it[u]++];
                int v = x.to, e = x.id;
                if (e == pe[u]) continue; // parent EDGE, not parent vertex
                if (!dfn[v]) {
                    parent[v] = u; pe[v] = e;
                    es.push_back(e);
                    dfn[v] = low[v] = ++timer;
                    stack.push_back(v);
                } else if (dfn[v] < dfn[u]) {
                    es.push_back(e);
                    low[u] = min(low[u], dfn[v]);
                }
            } else {
                stack.pop_back();
                int p = parent[u];
                if (p >= 0) {
                    low[p] = min(low[p], low[u]);
                    if (low[u] >= dfn[p]) {
                        int b = (int)out.begin.size() - 1, e;
                        do {
                            e = es.back(); es.pop_back();
                            out.id[e] = b;
                            out.edges.push_back(e);
                        } while (e != pe[u]);
                        out.begin.push_back((int)out.edges.size());
                    }
                }
            }
        }
    }
    return out;
}

struct Path {
    vector<int> v, e;
    i64 length = -1;
};
struct Separator {
    vector<int> v, e, chord;
};

class Solver {
    Graph g;
    int s, t, n, m;
    vector<unsigned char> bad;
    vector<Separator> sep;
    vector<int> ownerE, indexE, ownerV, indexV;
    // Scratch space for reconstructing a path from a candidate edge set.
    vector<int> degree, first, second, touched;

    bool reduce() {
        vector<int> eu(m), ev(m);
        for (int i = 0; i < m; ++i) eu[i] = g.e[i].u, ev[i] = g.e[i].v;
        Blocks b = biconnected(n, eu, ev);
        int nb = (int)b.begin.size() - 1;
        vector<vector<int>> tree(n + nb);
        vector<int> seen(n, -1);
        for (int c = 0; c < nb; ++c) {
            for (int j = b.begin[c]; j < b.begin[c + 1]; ++j) {
                auto x = g.e[b.edges[j]];
                for (int u : {x.u, x.v}) if (seen[u] != c) {
                    seen[u] = c;
                    tree[u].push_back(n + c);
                    tree[n + c].push_back(u);
                }
            }
        }
        vector<int> parent(n + nb, -1), q;
        parent[s] = s; q.push_back(s);
        for (size_t i = 0; i < q.size() && parent[t] < 0; ++i)
            for (int v : tree[q[i]]) if (parent[v] < 0)
                parent[v] = q[i], q.push_back(v);
        if (parent[t] < 0) return false;
        vector<unsigned char> on(n + nb);
        for (int u = t; ; u = parent[u]) { on[u] = 1; if (u == s) break; }
        bad.assign(n, 0);
        vector<int> deg(n);
        for (int c = 0; c < nb; ++c) if (on[n + c]) {
            if (b.begin[c + 1] - b.begin[c] == 1) return false;
            for (int j = b.begin[c]; j < b.begin[c + 1]; ++j) {
                auto x = g.e[b.edges[j]];
                ++deg[x.u]; ++deg[x.v];
            }
            for (int u : tree[n + c]) {
                // The two local terminals of this block are NOT bad.
                if (deg[u] == 2 && !on[u]) bad[u] = 1;
                deg[u] = 0;
            }
        }
        vector<Edge> keep;
        keep.reserve(m);
        for (int i = 0; i < m; ++i) if (b.id[i] >= 0 && on[n + b.id[i]])
            keep.push_back(g.e[i]);
        g = Graph(n, move(keep)); m = (int)g.e.size();
        ownerE.assign(m, -1); indexE.assign(m, -1);
        ownerV.assign(n, -1); indexV.assign(n, -1);
        degree.assign(n, 0); first.resize(n); second.resize(n);
        return true;
    }

    // Labels: (total weight, number of edges, reversed original-edge-id list).
    // The last component is an EXACT lexicographic order, not a random hash.
    // With two copies, equal last edges only require comparing the two copies
    // of the same predecessor. Those comparisons are memoized in linear time.
    Path shortest(const vector<unsigned char>& ban,
                  const vector<unsigned char>* masks = nullptr) const {
        bool two = masks != nullptr;
        int nn = two ? 2 * n : n;
        vector<i64> dist(nn, INF);
        vector<int> hops(nn, INT_MAX), pv(nn, -1), pe(nn, -1);
        vector<signed char> cmp(two ? n : 0, 2);
        vector<pair<int,int>> trail;
        auto compareCopies = [&](int a, int b) {
            if (a == b) return 0;
            int u = a % n;
            assert(b % n == u && two);
            trail.clear();
            int x = u;
            while (cmp[x] == 2) {
                int le = pe[x], he = pe[x + n];
                if (le != he) { cmp[x] = le < he ? -1 : 1; break; }
                int lp = pv[x], hp = pv[x + n];
                if (lp == hp) { cmp[x] = 0; break; }
                assert(lp >= 0 && hp >= 0 && lp % n == hp % n);
                trail.push_back({x, lp < n ? 1 : -1});
                x = lp % n;
            }
            int c = cmp[x];
            for (int j = (int)trail.size() - 1; j >= 0; --j) {
                c *= trail[j].second;
                cmp[trail[j].first] = (signed char)c;
            }
            return a < n ? (int)cmp[u] : -(int)cmp[u];
        };
        struct Item {
            i64 d; int h, v;
            bool operator<(const Item& x) const {
                if (d != x.d) return d > x.d;
                if (h != x.h) return h > x.h;
                return v > x.v;
            }
        };
        priority_queue<Item> pq;
        dist[s] = 0; hops[s] = 0; pq.push({0, 0, s});
        while (!pq.empty()) {
            auto z = pq.top(); pq.pop();
            int x = z.v, u = x % n, layer = x / n;
            if (z.d != dist[x] || z.h != hops[x]) continue;
            if (x == t) break;
            for (int ai = g.off[u]; ai < g.off[u + 1]; ++ai) {
                Arc a = g.a[ai];
                if (bad[a.to] || (!ban.empty() && ban[a.id])) continue;
                int options = two ? (((*masks)[ai] >> (2 * layer)) & 3) : 1;
                for (int l = 0; l < 2; ++l) if (options & (1 << l)) {
                    int v = a.to + l * n;
                    i64 nd = z.d + g.e[a.id].w;
                    int nh = z.h + 1;
                    if (nd < dist[v] || (nd == dist[v] && nh < hops[v])) {
                        dist[v] = nd; hops[v] = nh; pv[v] = x; pe[v] = a.id;
                        pq.push({nd, nh, v});
                    } else if (nd == dist[v] && nh == hops[v]) {
                        bool better = a.id < pe[v];
                        if (a.id == pe[v]) {
                            int c = compareCopies(x, pv[v]);
                            better = c < 0 || (c == 0 && x < pv[v]);
                        }
                        if (better) pv[v] = x, pe[v] = a.id;
                    }
                }
            }
        }
        Path p;
        if (dist[t] == INF) return p;
        p.length = dist[t];
        for (int v = t; ; v = pv[v]) {
            p.v.push_back(v % n);
            if (v == s) break;
            p.e.push_back(pe[v]);
        }
        reverse(p.v.begin(), p.v.end()); reverse(p.e.begin(), p.e.end());
        return p;
    }

    bool nonseparating(const Path& p) const {
        vector<unsigned char> removed(m);
        for (int e : p.e) removed[e] = 1;
        DSU d(n);
        for (int i = 0; i < m; ++i) if (!removed[i])
            d.unite(g.e[i].u, g.e[i].v);
        int r = d.find(s);
        for (auto e : g.e) if (d.find(e.u) != r || d.find(e.v) != r) return false;
        return true;
    }

    bool useful(Separator& r) const {
        if (r.e.size() < 3) return false;
        r.chord.clear();
        for (int i = 0; i + 2 < (int)r.v.size(); ++i) {
            int e = g.edgeId(r.v[i], r.v[i + 2]);
            if (e < 0 || (i64)g.e[r.e[i]].w + g.e[r.e[i + 1]].w >= g.e[e].w)
                return false;
            r.chord.push_back(e);
        }
        return true;
    }

    void addSeparator(Separator r) {
        int old = ownerE[r.e[0]];
        if (old >= 0) {
            assert(sep[old].v == r.v);
            return;
        }
        int id = (int)sep.size();
        for (int i = 0; i < (int)r.e.size(); ++i) {
            assert(ownerE[r.e[i]] < 0);
            ownerE[r.e[i]] = id; indexE[r.e[i]] = i;
        }
        for (int i = 1; i + 1 < (int)r.v.size(); ++i) {
            assert(ownerV[r.v[i]] < 0 && r.v[i] != s && r.v[i] != t);
            ownerV[r.v[i]] = id; indexV[r.v[i]] = i;
        }
        sep.push_back(move(r));
    }

    bool makePath(const vector<int>& es, Separator& r) {
        touched.clear();
        bool ok = true;
        for (int e : es) for (int u : {g.e[e].u, g.e[e].v}) {
            if (degree[u] == 0) touched.push_back(u), first[u] = e;
            else if (degree[u] == 1) second[u] = e;
            else ok = false;
            ++degree[u];
        }
        int start = -1, ends = 0;
        for (int u : touched) if (degree[u] == 1) ++ends, start = u;
        ok &= ends == 2 && touched.size() == es.size() + 1;
        if (ok) {
            r.v.clear(); r.e.clear();
            int u = start, prev = -1;
            for (size_t j = 0; j <= es.size(); ++j) {
                r.v.push_back(u);
                int e = first[u] != prev ? first[u] : (degree[u] == 2 ? second[u] : -1);
                if (e < 0) break;
                r.e.push_back(e);
                u ^= g.e[e].u ^ g.e[e].v; prev = e;
            }
            ok = r.e.size() == es.size() && r.v.size() == es.size() + 1;
        }
        for (int u : touched) degree[u] = 0;
        return ok;
    }

    // Find S-separators for the supplied orientation of P. Running again with
    // reversed P finds T-separators. 'parity' is the parity being CONTRACTED.
    void collectST(const Path& p, bool reversed, vector<unsigned char>& ban) {
        vector<int> pos(n, -1), mn(n, n), eu(m), ev(m);
        for (int i = 0; i < (int)p.v.size(); ++i) pos[p.v[i]] = i;
        for (int u = 0; u < n; ++u) {
            if (pos[u] >= 0) mn[u] = pos[u];
            for (int j = g.off[u]; j < g.off[u + 1]; ++j)
                if (pos[g.a[j].to] >= 0) mn[u] = min(mn[u], pos[g.a[j].to]);
        }
        vector<int> head(n, -1), next(2 * m), vertices, es;
        for (int parity = 0; parity < 2; ++parity) {
            DSU d(n);
            for (int i = parity; i + 2 < (int)p.v.size(); i += 2)
                if (g.edgeId(p.v[i], p.v[i + 2]) >= 0) d.unite(p.v[i], p.v[i + 2]);
            for (int u = 0; u < n; ++u) if (pos[u] < 0)
                for (int j = g.off[u]; j < g.off[u + 1]; ++j) {
                    int v = g.a[j].to;
                    if (pos[v] >= 0 && (pos[v] & 1) == parity && pos[v] != mn[u])
                        d.unite(u, v);
                }
            for (int i = 0; i < m; ++i)
                eu[i] = d.find(g.e[i].u), ev[i] = d.find(g.e[i].v);
            Blocks b = biconnected(n, eu, ev);
            for (int c = 0; c + 1 < (int)b.begin.size(); ++c) {
                vertices.clear();
                for (int j = b.begin[c]; j < b.begin[c + 1]; ++j) {
                    int e = b.edges[j];
                    for (int k = 0; k < 2; ++k) {
                        int u = k ? ev[e] : eu[e], a = 2 * e + k;
                        if (head[u] < 0) vertices.push_back(u);
                        next[a] = head[u]; head[u] = a;
                    }
                }
                for (int u : vertices) {
                    es.clear();
                    for (int a = head[u]; a >= 0; a = next[a]) es.push_back(a / 2);
                    head[u] = -1;
                    if (es.size() < 3) continue;
                    Separator r;
                    if (!makePath(es, r)) continue;
                    auto oriented = [&]() {
                        int last = -1;
                        for (int v : r.v) if (pos[v] >= 0) {
                            if (pos[v] <= last) return false;
                            last = pos[v];
                        }
                        if (pos[r.v[2]] < 0 || (pos[r.v[2]] & 1) == parity) return false;
                        for (int i = 3; i < (int)r.v.size(); ++i)
                            if (pos[r.v[i]] != pos[r.v[i - 1]] + 1) return false;
                        // If r[0] is off P but r[1] is on P, reaching r[0]
                        // through r[1] and then traversing r repeats r[1].
                        // Thus r is NOT traversable. The bare minimum-neighbor
                        // test alone (paper Theorem 6.3) is insufficient here.
                        if (pos[r.v[0]] < 0 && pos[r.v[1]] >= 0) return false;
                        return mn[r.v[0]] < pos[r.v[2]];
                    };
                    if (!oriented()) {
                        reverse(r.v.begin(), r.v.end()); reverse(r.e.begin(), r.e.end());
                        if (!oriented()) continue;
                    }
                    if (!useful(r)) continue;
                    ban[r.e.back()] = 1;
                    if (reversed) {
                        reverse(r.v.begin(), r.v.end()); reverse(r.e.begin(), r.e.end());
                        reverse(r.chord.begin(), r.chord.end());
                    }
                    addSeparator(move(r));
                }
            }
        }
    }

    void collectExtra(const Path& p) {
        vector<unsigned char> removed(m);
        for (int e : p.e) removed[e] = 1;
        DSU d(n);
        for (int i = 0; i < m; ++i) if (!removed[i]) d.unite(g.e[i].u, g.e[i].v);
        vector<int> c(p.v.size());
        for (int i = 0; i < (int)p.v.size(); ++i) c[i] = d.find(p.v[i]);
        auto take = [&](int l, int r) {
            if (r - l < 3) return;
            Separator x;
            x.v.assign(p.v.begin() + l, p.v.begin() + r + 1);
            x.e.assign(p.e.begin() + l, p.e.begin() + r);
            if (useful(x)) addSeparator(move(x));
        };
        int l = 0;
        for (int j = 1; j < (int)c.size(); ++j) {
            if (j > 1 && c[j] != c[j - 2]) { take(l, j - 1); l = j - 1; }
            if (c[j] == c[j - 1]) l = j;
        }
        take(l, (int)c.size() - 1);
    }

    int position(int r, int v) const {
        if (r < 0) return -1;
        if (sep[r].v.front() == v) return 0;
        if (sep[r].v.back() == v) return (int)sep[r].e.size();
        return ownerV[v] == r ? indexV[v] : -1;
    }

    vector<unsigned char> buildMasks() const {
        vector<int> eu(m, -1), ev(m, -1);
        for (int e = 0; e < m; ++e) if (ownerE[e] < 0)
            eu[e] = g.e[e].u, ev[e] = g.e[e].v;
        Blocks b = biconnected(n, eu, ev);
        // At inner vertex u, replace an edge removed by ANOTHER separator by
        // that separator's endpoint-to-second-vertex chord (Section 6.1.2).
        auto replacement = [&](int u, int e) {
            int r = ownerE[e];
            if (r < 0) return e;
            const auto& q = sep[r];
            if (u == q.v.front()) return q.chord.front();
            assert(u == q.v.back());
            return q.chord.back();
        };
        auto leftmost = [&](int v, int e) {
            int r = ownerV[v], i = indexV[v];
            if (i < 2) return true;
            int f = replacement(v, e), h = sep[r].chord[i - 2];
            assert(b.id[f] >= 0 && b.id[h] >= 0);
            return b.id[f] != b.id[h];
        };
        auto rightmost = [&](int u, int e) {
            int r = ownerV[u], i = indexV[u];
            if (i + 2 >= (int)sep[r].v.size()) return true;
            int f = replacement(u, e), h = sep[r].chord[i];
            assert(b.id[f] >= 0 && b.id[h] >= 0);
            return b.id[f] != b.id[h];
        };
        vector<unsigned char> mask(g.a.size());
        for (int u = 0; u < n; ++u) if (!bad[u])
            for (int a = g.off[u]; a < g.off[u + 1]; ++a) {
                int v = g.a[a].to, e = g.a[a].id;
                if (bad[v]) continue;
                int ru = ownerV[u], rv = ownerV[v], re = ownerE[e];
                int vp = position(ru, v), up = position(rv, u);
                bool enter = rv >= 0 && up < 0 && leftmost(v, e);
                bool leave = ru >= 0 && vp < 0 && rightmost(u, e);
                bool head = re >= 0 && indexE[e] == 0 && sep[re].v[0] == u;
                bool tail = re >= 0 && indexE[e] + 1 == (int)sep[re].e.size()
                            && sep[re].v.back() == v;
                bool back1 = ru >= 0 && indexV[u] >= 2 && vp == indexV[u] - 1;
                bool back2 = ru >= 0 && indexV[u] >= 2 && vp == indexV[u] - 2;
                unsigned char z = 0;
                if (!head && !enter) z |= 1; // low -> low
                if (head || (rv >= 0 && up < 0 && indexV[v] == (int)sep[rv].e.size() - 2))
                    z |= 2; // low -> high; includes the |r|-3 endpoint exception
                if (ru >= 0 && re < 0 && !back2 && !enter && !leave) z |= 4; // high -> low
                if (ru >= 0 && rv >= 0 && !tail && !back1 && !back2 && !leave) z |= 8; // high -> high
                mask[a] = z;
            }
        return mask;
    }

public:
    Solver(int n_, vector<Edge> edges, int s_, int t_)
        : g(n_, move(edges)), s(s_), t(t_), n(n_), m((int)g.e.size()) {}
    Path solve() {
        if (!reduce()) return {};
        Path p = shortest({});
        assert(p.length >= 0);
        if (nonseparating(p)) return p;
        vector<unsigned char> ban(m);
        collectST(p, false, ban);
        reverse(p.v.begin(), p.v.end()); reverse(p.e.begin(), p.e.end());
        collectST(p, true, ban);
        Path p0 = shortest(ban);
        assert(p0.length >= 0);
        collectExtra(p0);
        auto mask = buildMasks();
        Path ans = shortest({}, &mask);
        assert(ans.length >= 0);
#ifdef ROAD_VALIDATE
        assert(nonseparating(ans));
        vector<int> seen(n);
        for (int v : ans.v) { assert(!seen[v]); seen[v] = 1; }
#endif
        return ans;
    }
};
} // namespace road

#ifndef ROAD_NO_MAIN
class FastInput {
    static constexpr int B = 1 << 16;
    char data[B]; int pos = 0, len = 0;
    int get() {
        if (pos == len) { len = (int)fread(data, 1, B, stdin); pos = 0; }
        return pos == len ? EOF : data[pos++];
    }
public:
    bool read(int& x) {
        int c;
        do { c = get(); if (c == EOF) return false; } while (c <= ' ');
        x = 0;
        do { x = x * 10 + c - '0'; c = get(); } while (c >= '0' && c <= '9');
        return true;
    }
};
int main() {
    FastInput in;
    int n, m;
    if (!in.read(n) || !in.read(m)) return 0;
    vector<road::Edge> edges(m);
    for (auto& e : edges) { in.read(e.u); in.read(e.v); in.read(e.w); --e.u; --e.v; }
    int s, t; in.read(s); in.read(t); --s; --t;
    road::Solver solver(n, move(edges), s, t);
    printf("%lld\n", solver.solve().length);
}
#endif