import strutils
import sequtils
import algorithm
import math
import queues
import tables
import sets
import logging
import future
const INF* = int(1e18 + 373)
proc readSeq*(): seq[string] = stdin.readLine().strip().split()
proc readSeq*(n: Natural): seq[string] =
result = newSeq[string](n)
for i in 0..<n:
result[i] = stdin.readLine().strip()
proc readInt1*(): int = readSeq().map(parseInt)[0]
proc readInt2*(): (int, int) =
let a = readSeq().map(parseInt)
return (a[0], a[1])
proc readInt3*(): (int, int, int) =
let a = readSeq().map(parseInt)
return (a[0], a[1], a[2])
proc readInt4*(): (int, int, int, int) =
let a = readSeq().map(parseInt)
return (a[0], a[1], a[2], a[3])
type seq2*[T] = seq[seq[T]]
proc newSeq2*[T](n1, n2: Natural): seq2[T] = newSeqWith(n1, newSeq[T](n2))
#------------------------------------------------------------------------------#
type UnionFindTree = tuple[ p, h, w: seq[int] ]
proc initUnionFindTree(n: int): UnionFindTree =
var p = newSeq[int](n)
p.fill(-1)
var h = newSeq[int](n)
h.fill(0)
var w = newSeq[int](n)
w.fill(1)
return (p, h, w)
proc find(this: var UnionFindTree, v: int): int =
if this.p[v] == -1:
return v
this.p[v] = find(this, this.p[v])
return this.p[v]
proc same(this: var UnionFindTree, u, v: int): bool =
this.find(u) == this.find(v)
proc union(this: var UnionFindTree, u, v: int) =
let uRoot = this.find(u)
let vRoot = this.find(v)
if uRoot == vRoot:
return
if this.h[uRoot] > this.h[vRoot]:
this.p[vRoot] = uRoot
this.w[uRoot] += this.w[vRoot]
else:
this.p[uRoot] = vRoot
this.w[vRoot] += this.w[uRoot]
if this.h[uRoot] == this.h[vRoot]:
this.h[vRoot] += 1
proc reduceL[T1, T2](a: seq[T1]; e: T2; f: (T2, T1) -> T2): T2 =
var ans = e
for i in 0..<a.len():
ans = f(ans, a[i])
return ans
#------------------------------------------------------------------------------#
type Pred1[T] = T -> bool
# [lb, ub)
proc nibutanLb(lb, ub: int; f: Pred1[int]): int =
var lb = lb
var ub = ub
while ub - lb > 1:
let mid = (ub + lb) div 2
if f(mid):
lb = mid
else:
ub = mid
return lb
# (lb, ub]
proc nibutanUb(lb, ub: int; f: Pred1[int]): int =
var lb = lb
var ub = ub
while ub - lb > 1:
let mid = (ub + lb) div 2
if f(mid):
ub = mid
else:
lb = mid
return ub
#------------------------------------------------------------------------------#
type Edge = tuple [ a, b, c: int ]
proc compareEdgeByWeight(e1, e2: Edge): int =
if e1.c == e2.c:
return 0
elif e1.c > e2.c:
return 1
else:
return -1
proc minimum_spanning_tree(n: int; es: seq[Edge]): seq[Edge] =
let es = es.sorted(compareEdgeByWeight)
var uft = initUnionFindTree(n)
var ans = newSeq[Edge](0)
for e in es:
if ans.len() >= n - 1:
break
if not uft.same(e.a, e.b):
ans.add(e)
uft.union(e.a, e.b)
return ans
proc buildRootedTree(n: int; es: seq[Edge]): seq[Edge] =
var g = newSeq2[(int, int)](n, 0)
for e in es:
g[e.a].add((e.b, e.c))
g[e.b].add((e.a, e.c))
var ans = newSeq[Edge](n)
var stack = newSeq[int](0)
var used = newSeq[bool](n)
stack.add(0)
used[0] = true
ans[0] = (0, 0, 0)
while stack.len() != 0:
let v = stack.pop()
for e in g[v]:
if used[e[0]]:
continue
used[e[0]] = true
stack.add(e[0])
ans[e[0]] = (e[0], v, e[1])
return ans
proc parent(pps: seq2[Edge]; v, i: int): int =
var u = v
var j = i
var k = 0
while j != 0:
if (j and 1) != 0:
u = pps[k][u].b
j = j div 2
k += 1
return u
proc parentMaxEdge(pps: seq2[Edge]; v, i: int): int =
var u = v
var j = i
var ans = -1
var k = 0
while j != 0:
if (j and 1) != 0:
ans = max(ans, pps[k][u].c)
u = pps[k][u].b
j = j div 2
k += 1
return ans
proc depth(pps: seq2[Edge]; v: int): int =
nibutanUb(-1, 2^12, it => parent(pps, v, it) == 0)
proc lca(pps: seq2[Edge]; d: seq[int]; v, u: int): int =
var v = v
var u = u
if d[v] < d[u]:
swap(v, u)
v = parent(pps, v, d[v] - d[u])
let diff = nibutanUb(-1, 2^12, it => parent(pps, v, it) == parent(pps, u, it))
return parent(pps, v, diff)
proc main() =
let (n, m) = readInt2()
var es = newSeq[Edge](m)
for i in 0..<m:
let (a, b, c) = readInt3()
es[i] = (a - 1, b - 1, c)
let q = readInt1()
var qs = newSeq[(int, int)](q)
for i in 0..<q:
let (s, t) = readInt2()
qs[i] = (s - 1, t - 1)
let mst = minimum_spanning_tree(n, es)
let mstSum = mst.reduceL(0, (acc, e) => (acc + e.c))
let ps = buildRootedTree(n, mst)
var pps = newSeq2[Edge](13, n)
pps[0] = ps
for i in 1..12:
for v in 0..<n:
let parent = pps[i - 1][pps[i - 1][v].b].b
let maxWeight = max(pps[i - 1][v].c, pps[i - 1][pps[i - 1][v].b].c)
pps[i][v] = (v, parent, maxWeight)
var d = newSeq[int](n)
for v in 0..<n:
d[v] = depth(pps, v)
for q in qs:
let a = lca(pps, d, q[0], q[1])
var ans = 0
ans = max(ans, parentMaxEdge(pps, q[0], d[q[0]] - d[a]))
ans = max(ans, parentMaxEdge(pps, q[1], d[q[1]] - d[a]))
echo mstSum - ans
main()