Mars Life Tree

20XX, the lives, or fossils, more exactly, on the Mars, which is founded on a totally different life type to the Earth one are found by human beings. MLT, or Mars Life Tree, thought to be the breeder of all lives on the Mars is discovered as a fossil too, is proved there used to have extremely complex types of life.
There is an extremely huge MLT under the surface of the Mars, is not a real tree, but variety of carbon-based protein balls(called “node”) connected by neuron links(called “edge”), formed a tree like structure, which is peer-to-peer reachable and non-circled. However, scientist discovered that the MLT is able to grow and mutate from basically two nodes with one edge. The mutation refers that a node is able to mutate to another kind of node and, costs some energy. And the growing means that one node can reach out a new edge and grows a new node at the other end of the edge, of course spend energy. Luckily, the energy costs of every kind of mutation and growing are measured and calculated.
Since scientists found out that different shape of MLT may give a birth to different kinds of lives, they believe that the earliest two node, called roots, directly connect to an organ like a lair to bear lives, which is air-slaked and become untraceable in the fossil.
Assuming the MLT grows obeying the rule of costing least energy, your mission is find out the roots in the fossil, point out the initial status of these two nodes, and calculate the total energy may cost during the evolvement.

There may be multiple test cases.
There are two integers n (n<=1000) and m (m<=10) in the first line means the counts of nodes of the MLT, and counts of kinds of nodes.
There are n integers Ki (1<=Ki<=m) in the second line, figure out that the ith node is one of kind Ki.
Then followed two integers S1, S2, (1<=S1, S2<=m), shows the type of the two nodes at the beginning.
A m*m matrix U followed, for every element Uij (Uij<100) in row i column j, refers the mutate energy cost from type i to type j.
Then there are m numbers P1 … Pm (Pi<100), Pi refers the energy cost of reaching out a new edge and node end by type i.
Then n-1 lines follows, two integers in each line x, y, (1<=x, y<=n, x≠y) means that node i and j are connected by a edge.

For each test case:
One integer in the first line refers the link ID of the roots.
Second line contains one integer refers the minimal total cost growing the MLT.
Then a blank line followed.

3 3
1 2 3
1 1
0 1 3
1 0 1
3 1 0
1 1 3
2 3
1 2

2
3

2009 Multi-University Training Contest 17 - Host by NUDT