Problem:
 Score : 700 points    Problem Statement Takahashi found an undirected connected graph with N vertices and M edges. The vertices are numbered 1 through N . The i -th edge connects vertices a_i and b_i , and has a weight of c_i .  He will play Q rounds of a game using this graph. In the i -th round, two vertices S_i and T_i are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices S_i or T_i by traversing chosen edges.  For each round, find the minimum possible total weight of the edges chosen by Takahashi.      Constraints  1 ≦ N ≦ 4,000  1 ≦ M ≦ 400,000  1 ≦ Q ≦ 100,000  1 ≦ a_i,b_i,S_i,T_i ≦ N  1 ≦ c_i ≦ 10^{9}  a_i \neq b_i  S_i \neq T_i  The given graph is connected.       Partial Scores  In the test set worth 200 points, Q = 1 .  In the test set worth another 300 points, Q ≦ 3000 .         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2 : a_M  b_M  c_M  Q  S_1  T_1  S_2  T_2 : S_Q  T_Q       Output Print Q lines. The i -th line should contain the minimum possible total weight of the edges chosen by Takahashi.        Sample Input 1 4 3
1 2 3
2 3 4
3 4 5
2
2 3
1 4      Sample Output 1 8
7  We will examine each round:   In the 1 -st round, choosing edges 1 and 3 achieves the minimum total weight of 8 .  In the 2 -nd round, choosing edges 1 and 2 achieves the minimum total weight of 7 .        Sample Input 2 4 6
1 3 5
4 1 10
2 4 6
3 2 2
3 4 5
2 1 3
1
2 3      Sample Output 2 8  This input satisfies the additional constraints for both partial scores.

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a-1, b-1))
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

L = 2*N-1
G = [[]] * L
C = [0]*L
*lb, = range(N)
cur = N

s = 0
for c, a, b in E:
    pa = root(a); pb = root(b)
    if pa == pb:
        continue
    s += c
    chds = [lb[pa], lb[pb]]
    if pa < pb:
        p[pb] = pa
        lb[pa] = cur
    else:
        p[pa] = pb
        lb[pb] = cur
    C[cur] = c
    G[cur] = chds
    cur += 1

H = [0]*L
prv = [-1]*L
def dfs(v):
    s = 1; heavy = -1; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(L-1)

SS = []
D = []
LB = [0]*L
I = [0]*L
que = deque([(L-1, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v != -1:
        I[v] = len(S)
        S.append(v)
        LB[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


def query(u, v):
    lu = LB[u]; lv = LB[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = LB[v]

    while lu != lv:
        u = prv[SS[lu][0]]
        lu = LB[u]

        v = prv[SS[lv][0]]
        lv = LB[v]

    return u if I[u] < I[v] else v


def gen():
    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        w = query(u-1, v-1)
        yield "%d\n" % (s - C[w])
ans = list(gen())
sys.stdout.writelines(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from collections import deque

class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  
        return self.find(x) == self.find(y)


N,M=map(int,input().split())
table=[[int(i) for i in input().split()]for i in range(M)]
Q=int(input())
query=[[int(i) for i in input().split()]for i in range(Q)]
table = sorted(table,key=itemgetter(2))
if N<3:
    for a,b in query:
        print(0)
    sys.exit()
T=Unionfindtree(N)
sear=Unionfindtree(2*N-1)
ans=0
value=[0]*(N+N-1)
dp=[[0]*(2*N-1) for i in range(16)]
table2=[[] for i in range(2*N-1)]
s=0
for i in range(M):
    a,b,c=table[i]
    a,b=a-1,b-1
    if not T.connect(a,b):
        ans+=c
        T.union(a,b)
        value[s+N]=c
        le=a
        ri=b
        for j in range(s+N,N-1,-1):
            if sear.connect(a,j):
                le=j
                break
        for j in range(s+N,N-1,-1):
            if sear.connect(b,j):
                ri=j
                break
        table2[s+N].append(le)
        table2[s+N].append(ri)
        sear.union(le,s+N)
        sear.union(ri,s+N)
        s+=1
    if s==N-1:
        break

H=deque()
H.append((0,2*N-2))
depth=[-1]*(2*N-1)
depth[2*N-2]=0
while H:
    dep,pt=H.popleft()
    for p in table2[pt]:
        H.append((dep+1,p))
        depth[p]=dep+1
        dp[0][p]=pt



for k in range(1,16):
    for x in range(2*N-1):
        dp[k][x]=dp[k-1][dp[k-1][x]]
def LCA(s,t):
    if depth[s]>depth[t]:
        s,t=t,s
    for k in range(16):
        if ((depth[t]-depth[s] )>>k) & 1:
            t = dp[k][t]
    if s==t:
        return s
    for k in range(15,-1,-1):
        if dp[k][s]!=dp[k][t]:
            s=dp[k][s]
            t=dp[k][t]
    return dp[0][s]

for s,t in query:
    s,t=s-1,t-1
    pa=LCA(s,t)
    
    print(ans-value[pa])