2346: 道路规划

有  个村庄，编号从  到  ，请你建立一些道路，使得任意两个村庄可以相连。我们说两个村  和  是相连的，当且仅当有一条公路在  与 之间,或存在一个村庄 ，有一条的道路连接着  和  之间,一条连接着  和  。

我们知道，已经有一些道路在一些村庄之间，你的工作是再建一些道路，使得所有的村庄连接并且所有的道路建造总和最低。

第一行是一个整数  ()，表示村庄的数量。

接下来  行，每行包含  个整数，在这  行中的第  行的第  个整数  表示村庄  到村庄  建立道路的费用 ()。

然后有一个整数  ()。

接下来再  行，每一行包含两个整数  和  ()，即村庄  和  之间已经建成道路。

3
0 990 692
990 0 179
692 179 0
1
1 2

179