I. W/S TREE
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes. Each node $$$i$$$ (where $$$1 \le i \le n$$$) has a treasure with value $$$a_i$$$. The edges connecting the nodes are of two types: strong or weak.

You start exploring this tree from node 1. You want to find a walk (a sequence of connected nodes) starting at node 1 that maximizes the total value of treasures collected. The treasure at a node is collected the first time you visit that node. Subsequent visits to the same node do not yield any more treasure value.

The rules for traversing the edges depend on their type:

  • A strong edge can be traversed any number of times, in either direction.
  • A weak edge can be traversed at most once in total during your entire walk. For instance, if there is a weak edge between nodes $$$u$$$ and $$$v$$$, you can traverse it once from $$$u$$$ to $$$v$$$, or once from $$$v$$$ to $$$u$$$. After using it once in either direction, you cannot use this specific weak edge again.

Your walk can finish at any node in the tree. Determine the maximum possible sum of treasure values you can collect.

NOTE: When you step into the node, you can't skip the treasure you must collect it.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case begins with a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of nodes in the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the value of the treasure at each node.

The next $$$n-1$$$ lines describe the edges. Each line contains three integers $$$u, v, s$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$s \in \{0, 1\}$$$), representing an edge between node $$$u$$$ and node $$$v$$$. If $$$s=0$$$, the edge is weak. If $$$s=1$$$, the edge is strong.

It is guaranteed that the given graph is a tree. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print a single line containing one integer — the maximum total value of treasures that can be collected starting from node 1.

Example
Input
2
5
1 1 1 1 1
1 2 0
1 3 1
1 4 1
2 5 1
3
1 2 3
1 2 0
1 3 0
Output
5
4