#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; struct LCA{ vector> g; vector d; vector> p; int log; int n; LCA(const vector> &g):n(g.size()), g(g), d(g.size()){ log=0; while(1<(n)); } void dfs(int x, int prev){ for(auto y:g[x]){ if(y==prev) continue; d[y]=d[x]+1; p[0][y]=x; dfs(y, x); } } void build(){ dfs(0, -1); for(int i=1; id[b]) swap(a, b); int dd=d[b]-d[a], i=0; int a1=a, b1=b; while(dd){ if(dd&1) b1=p[i][b1]; dd>>=1; i++; } if(a1==b1) return a1; for(int j=log-1; j>=0; j--){ if(p[j][a1]!=p[j][b1]){ a1=p[j][a1], b1=p[j][b1]; } } return p[0][a1]; } int dist(int a, int b){ return d[a]+d[b]-2*d[lca(a, b)]; } }; int a[100010], b[100010]; ll c[100010]; vector

g[100010]; vector

g1[100020]; ll d1[10][100020]; ll d[100010]; void dfs(int x, int p){ for(auto q:g[x]){ int y=q.first; if(y==p) continue; d[y]=d[x]+q.second; dfs(y, x); } } int main() { int n, k; cin>>n>>k; vector> gt(n); for(int i=0; i>a[i]>>b[i]>>c[i]; a[i]--; b[i]--; gt[a[i]].push_back(b[i]); gt[b[i]].push_back(a[i]); g[a[i]].push_back({b[i], c[i]*2}); g[b[i]].push_back({a[i], c[i]*2}); g1[a[i]].push_back({b[i], c[i]*2}); g1[b[i]].push_back({a[i], c[i]*2}); } for(int i=0; i>m>>p; for(int j=0; j>x; x--; g1[x].push_back({i+n, p}); g1[i+n].push_back({x, p}); } } const ll INF=1e18; for(int i=0; i, greater

> que; fill(d1[i], d1[i]+n+k, INF); d1[i][i+n]=0; que.push({0, i+n}); while(!que.empty()){ auto p=que.top(); que.pop(); int x=p.second; if(d1[i][x]d1[i][x]+q.second){ d1[i][y]=d1[i][x]+q.second; que.push({d1[i][y], y}); } } } } LCA lca(gt); lca.build(); dfs(0, -1); int q; cin>>q; while(q--){ int u, v; cin>>u>>v; u--; v--; ll ans=d[u]+d[v]-2*d[lca.lca(u, v)]; for(int i=0; i