Surround the Islands

Farmer John (FR's cousin) has bought property in the Caribbean
and is going to try to raise dairy cows on a big farm composed
of islands. Set in his ways, he wants to surround all the islands
with a fence.

Each island in the farm has the shape of a polygon. He fences the
islands one side at a time (between a consecutive pair of vertices)
and proceeds clockwise around a given island with his fencing
operations. Since he wants to fence all the islands, he must at
some point travel to each other island using a boat.

FJ needs to choose a "central" island that will serve as
a home base. On this home-base island, he can start fencing
at any vertex and, at any vertex he encounters,
travel to some vertex on another island. When he travels to 
an island that is not the home-base, FJ will fence all the way
around it, and then IMMEDIATELY return back to the same vertex on the original island using the same path he traveled before.
Each boat trip has a cost; FJ knows the waters well, and so
knows these costs.

The islands are described by a set of N (3 <= N <= 500) pairs of
vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) -- although FJ needs
help in assembling these vertices into islands. The vertices are conveniently numbered 1..N.

The cost of traveling by boat between each pair of vertices is given
by a symmetric cost matrix whose elements fall in the range 0..1000.

What is the minimum cost of surrounding the islands with the fence?

PROBLEM NAME: surround.X

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Each line describes an island's border with two
        space-separated integers: V1 and V2

* Lines N+2..2*N+1: Line i-N-1 contains N integers that describe row i
        of the cost matrix: Row_i

SAMPLE INPUT:

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
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

INPUT DETAILS:

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
 xxxxxxxxxxx       11 xxxxxxxxxx 5
  xxxxxxx
   xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

The example describes three islands: {1,7,3,6,10}, {4,5,11} and
{2,9,8,12}. The travel costs are provided as a matrix. For example,
the travel cost from vertex 1 to 2 is 15.

OUTPUT FORMAT:

* Line 1: A single integer that specifies the minimum cost of building
        the fence

SAMPLE OUTPUT:

30

OUTPUT DETAILS:

There is more than one solution. One is: FJ starts from vertex 3
then 7 and stops at 1, travels to 11 followed by 4,5,11. He then
returns back to 1, and travels to 12 followed by 2,9,8,12. Finally,
he returns back to 1 and continues with 10,6,3,7. The costs are 8
* 2 = 16 for traveling from 1 to 11 and returning back, and 7 * 2
= 14 for traveling from 1 to 12 and back -- a total cost of 30.