小 A 是一个旅游爱好者。他来到了风景优美的太平洋，准备游览这里风景秀丽的小岛。
太平洋群岛是由 N 个小岛组成（编号为 1 \sim N），有些小岛之间通过双向的海上双向道路连接。从一个小岛出发，沿着这些双向道路能够到达的所有小岛构成了一个岛群。
每个小岛上都有酒店，小 A 可以在任何一个岛群中找一个小岛上的酒店办理入住，但确定好入住酒店后，就不会再更换酒店了。
接下来小 A 每天会选择：
游览一个岛群里的所有小岛。
回到酒店所在的小岛休息。
下一天会重复这个行程，直到玩遍所有的小岛。
已知，在一个岛群内，沿着海上道路，在不同的小岛之间游览不需要消耗任何费用。但如果坐快艇从一个小岛去往另一个小岛，需要支付快艇费。
请编程帮助小 A 计算出，他至少需要支付多少快艇费，才能完成此次旅游计划。
请注意：小 A 每天从酒店所在的岛群出发，选择一个目标岛群之后，他会从酒店所在岛群，直接去目标岛群。不会中途去其他岛群。
第 1 行输入整数 N，代表小岛的数量。
接下来 N 行，每行输入 2 个整数 U,V，表示编号为 U 和编号为 V 的小岛之间有一条双向的海上道路。
接下来 N 行，每行有 N 个整数，第 i 行的第 j 个整数代表了从编号为 i 的小岛出发，乘坐快艇到编号为 j 的小岛所需要支付的费用。测试数据确保 i 到 j 的费用和 j 到 i 的费用一定是相等的。
输出小 A 完成旅游计划需要支付的最少的快艇的费用。
12 2 9 3 6 6 10 10 1 2 12 8 9 8 12 11 5 5 4 11 4 1 7 7 3 0 15 9 20 25 8 10 13 17 8 8 7 15 0 12 12 10 10 8 15 15 8 8 9 9 12 0 25 20 18 16 14 13 7 12 12 20 12 25 0 8 13 14 15 15 10 10 10 25 10 20 8 0 16 20 18 17 18 9 11 8 10 18 13 16 0 10 9 11 10 8 12 10 8 16 14 20 10 0 18 20 6 16 15 13 15 14 15 18 9 18 0 5 12 12 13 17 15 13 15 17 11 20 5 0 22 8 10 8 8 7 10 18 10 6 12 22 0 11 12 8 8 12 10 9 8 16 12 8 11 0 9 7 9 12 10 11 12 15 13 10 12 9 0
30
6 1 2 2 3 1 3 4 5 5 6 4 6 0 8 3 4 1 6 8 0 9 5 2 7 3 9 0 5 3 9 4 5 5 0 4 2 1 2 3 4 0 9 6 7 9 2 9 0
2
该数据中，编号为 1,7,3,6,10 的小岛构成一个岛群，编号为 2,9,8,12 的小岛构成二个岛群，编号为 5,4,11 的小岛构成三个岛群。
最优方案有很多种。比如：小 A 可以在第 1 个岛群中的任意一家酒店办理入住。
第 1 天，他可以选择游玩第一个岛群中所有的小岛，不需要支付费用。
第 2 天，他可以从 1 号小岛出发，乘坐快艇到第二个岛群中的 12 号小岛，游览第二个岛群后，在从 12 号小岛回到 1 号小岛，往返费用为 7 \times 2。
第 3 天，他可以从 1 号小岛出发，乘坐快艇到第三个岛群中的 11 号小岛，游览第三个岛群后，在从 11 号小岛回到 1 号小岛，往返费用为 8 \times 2。
因此共需支付快艇费为 7 \times 2 + 8 \times 2 = 30。
对于 30\% 的数据，保证：1 \le N \le 100。
对于 100\% 的数据，保证：1 \le N \le 500，1 \le U,V \le N，任意两个小岛之间的快艇费用不超过 1000。