Meeting in Tree City

It's that time of year again for the Camp of the Panhellenic Informatics Competition. For the first time this year, the Camp is being organized in Tree City. Tree City is a real city in the land of algorithms, but it has a peculiarity: it resembles a tree (an acyclic connected graph). Specifically, Tree City has ~N~ vertices, numbered from ~1~ to ~N~, and some of these are connected by roads of various distances. It is certain that there is a unique path between any pair of vertices. Note that for the above to be true, the total number of roads must be ~N-1~.

This year, the Camp has many participants who have settled in some of the vertices of Tree City. Unfortunately, we have not yet found where the classes will be held, and that's why we need your help. We know exactly which vertices the participants are in, and in order to accommodate everyone, we want to find the vertex that minimizes the sum of distances from all the vertices where the participants are located.

Input:

In the first line of the input, a positive integer ~N~ is given, representing the number of vertices in Tree City. In the next line, there are ~N~ positive integers, where the ~i~-th integer is ~1~ if a participant is located at the ~i~-th vertex, otherwise it is ~0~. Following are ~N-1~ lines, each containing ~3~ numbers ~u~, ~v~, ~w~. Each such line represents a road between vertices ~u~ and ~v~, with a distance ~w~. Assume that the topology described is indeed that of a tree.

Output:

Print a line containing a positive integer: the minimum sum of distances from any vertex of the Tree City to all nodes where contestants are located.

Constraints:

• For test cases with a total value of 30%, it will be:
  1 ~\le~ Ν ~\le~ 5000, No additional constraints
• For test cases with a total value of 60%, it will be:
  1 ~\le~ Ν ~\le~ 500000, The number of vertices where a participant is staying is at most ~15~.
• For test cases with a total value of 100%, it will be:
  1 ~\le~ Ν ~\le~ 500000, No additional constraints

Example of Input - Ouput:

input:

7
0 0 1 1 1 0 1
1 2 1
1 3 3
1 4 2
2 7 4
3 5 1
3 6 7

output:

14

Explanation of the example:

The structure of the Tree City is shown below. There are four red vertices, ~3~, ~4~, ~5~, and ~7~, where contestants are located. The optimal choice we can make is to place the lessons at vertex ~1~, which has a distance of ~5~ from vertex ~7~, a distance of ~3~ from vertex ~3~, a distance of ~4~ from vertex ~5~, and a distance of ~2~ from vertex ~4~. Therefore, the total sum of distances of the contestants from this vertex is ~5 + 3 + 4 + 2 = 14~. It is easy to see that this is also the optimal answer.