auto sub4 = [&]() -> void {
        vector<vector<ll>> dp(22, vector<ll>(n + 5, INF));
        auto dijkstra = [&](int id, int source) -> void {
            dp[id][source] = 0;
            struct PQ {
                int u; ll w;
                bool operator < (const PQ & temp) const {
                    return w > temp.w;
                };
            };

            priority_queue<PQ> q;
            q.push({source, 0});

            while(!q.empty()) {
                int u = q.top().u;
                ll f = q.top().w;
                q.pop();

                if(dp[id][u] != f) continue;

                for(auto v : g[u]) {
                    if(minimize(dp[id][v.fi], dp[id][u] + v.se)) q.push({v.fi, dp[id][v.fi]});
                }
            }
        };

        for(int i = 0; i <= k; i++) {
            dijkstra(i * 2, a[i]);
            dijkstra(i * 2 + 1, b[i]);
        }

        struct PQ {
            int u; ll w;
            bool operator < (const PQ & temp) const {
                return w < temp.w;
            };
        };
        priority_queue<PQ> q;

        for(int i = 1; i <= n; i++) res[i] = -1;
        q.push({a[0], 0});
        res[a[0]] = 0;

        auto on_road = [&](int u, int v, int w) -> bool {
            if(dp[0][u] + dp[1][u] != dp[0][b[0]]) return false;
            if(dp[0][v] + dp[1][v] != dp[0][b[0]]) return false;
            if(dp[0][u] + w != dp[0][v]) return false;

            for(int i = 1; i <= k; i++) {
                if(dp[2 * i][u] + dp[2 * i + 1][u] != dp[2 * i][b[i]]) continue;
                if(dp[2 * i][v] + dp[2 * i + 1][v] != dp[2 * i][b[i]]) continue;
                if(dp[2 * i][u] + w != dp[2 * i][v]) continue;
                if(dp[0][u] != dp[2 * i][u]) continue;
                if(dp[0][v] != dp[2 * i][v]) continue;
                return true;
            }

            return false;
        };

        auto in_way = [&](int u, int v, int w) -> bool {
            if(dp[0][u] + w != dp[0][v]) return false;
            if(dp[0][u] + dp[1][u] != dp[0][b[0]]) return false;
            if(dp[0][v] + dp[1][v] != dp[0][b[0]]) return false;
            return true;
        };


        while(!q.empty()) {
            PQ T = q.top(); q.pop();
            int u = T.u;
            ll f = T.w;

            if(f != res[u]) continue;
            for(auto v : g[u]) {
                if(dp[0][u] + v.se == dp[0][v.fi] && on_road(u, v.fi, v.se)) {
                    if(maximize(res[v.fi], res[u] + v.se)) q.push({v.fi, res[v.fi]});
                } else if(in_way(u, v.fi, v.se)) {
                    if(maximize(res[v.fi], res[u])) q.push({v.fi, res[v.fi]});
                }
            }
        }

        ll ans = 0;
        for(int i = 1; i <= n; i++) maximize(ans, res[i]);
        cout << ans;
    };