有 $N$ 个村庄，编号 $1 \sim N$。
我们希望修建一些道路，使得任意两个村庄之间都能保持连通。
我们称村庄 $A$ 和村庄 $B$ 是相连的，当且仅当 $A$ 和 $B$ 之间存在一条道路，或者存在一个村庄 $C$ 使得 $A$ 和 $C$ 之间存在一条道路，并且 $C$ 和 $B$ 是相连的。
已知，一些村庄之间的道路已经修建好了。
你的任务是新修一些道路，使得任意两个村庄之间都能保持连通，并且新修的道路总长度尽可能短。

第一行包含整数 $N$，表示共有 $N$ 个村庄。
接下来 $N$ 行，每行包含 $N$ 个整数，其中第 $i$ 行第 $j$ 个数即为村庄 $i$ 与村庄 $j$ 之间的距离（即两村之间修路的长度）。
再一行包含一个整数 $Q$，表示共有 $Q$ 条已经修建好的道路。
接下来 $Q$ 行，每行包含两个整数 $a,b$，表示村庄 $a$ 和 $b$ 之间已经建有一条道路了。

输出一个整数，表示所需新修道路的最短总长度。

$3≤N≤100$,
$0≤Q≤$\frac{N(N−1)}{2}$,
$1≤a<b≤N$,
村庄之间距离 $[1,1,000]$。