Groundhog is very good at climbing trees.

One day, Groundhog came to an apple tree.For some reason, he decided to eat all the apples on the tree.There are  points on the apple tree, and there is an apple on each point. The points are connected by  edges (all the points are connected).On each edge there is an obstacle,which takes a certain amount of HP for Groundhog to jump over it.If Groundhog eats the  apple on the tree, he can restore  HP. He can go through a point where there are no apples.Groundhog can also rest for one unit of time to restore  HP.

Attention:The HP of Groundhog cannot be negative at any time, but it can be 0 or infinity.He can only eat an apple once, but every time he jumps over an edge, it consumes his HP. Groundhog takes no time to jump over obstacles or eat apples. Because the edges are fragile, Groundhog can only pass through each edge twice at most.

Now Groundhog starts to climb the tree from point , the root node of the tree, and his initial HP is zero.He wants to go back to point  after going through all the points. Since resting to restore his HP is very boring, he wants to ask you what the minimum resting time is for him to traverse all the points and get back to the root.

输入描述:

In the first line there is an interger  indicates that there are  datasets,and each of them contains:
An integer  in the first line indicates that there are  points on the apple tree.
The next line contains  integers, the  integer  indicates the HP that can be restored by eating the  apple.
The next  lines, each line contains three integers  , indicating there is an edge between  and ,with an obstacle that consumes  HP.

输出描述:

For each dataset,output an integer,indicating the minimum time for Groundhog to rest.

1
5
4 2 1 5 7
1 2 4
1 3 5
4 2 9
5 2 3

23

He can traverse in the order of .

备注:

.