나무꾼의 마을

미드가르드에는 $n$개의 마을이 도로망으로 연결되어 있다. 도로는 $n-1$개이며, 이 도로들을 따라 어느 마을에서든 다른 모든 마을로 갈 수 있다. 즉 도로망은 트리이다. 1번 마을이 수도이다. 미드가르드 사람들은 나무를 많이 베어 배를 만든다. 통치자는 올해 큰 함대를 건조해 새로운 땅과 자원을 정복하려고 한다. 이를 위해 다음 전략을 쓴다.

• 몇몇 마을에 총독을 보낸다. 총독을 보낸 마을에서 수도까지의 단순 경로 위에는 총독을 보낸 다른 마을이 없어야 한다. 수도에 총독을 보낼 수는 있지만, 그 경우 다른 어떤 마을에도 총독을 보낼 수 없다.
• 마을 $v$의 총독은 $v$를 지나 수도까지 가는 단순 경로를 가진 모든 마을을 관할한다. 마을 $v$ 자신도 포함된다.
• 총독의 관할에 들지 않은 마을 $i$는 한 해 동안 배를 $a_i$척 만든다.
• 마을 $v$에 총독이 있으면 다음과 같이 행동한다.
  • 관할 마을 중 $v$와 이웃한 마을들의 부분집합 $W$를 고른다. 그 마을들에 대형 조선소를 짓는다. 마을 $i$에 조선소를 지으려면 다른 마을 $b_i$개에서 나무를 공급받아야 하며, 그 조선소는 한 해 동안 배를 $c_i$척 만든다.
  • 그다음 관할 마을 중 나머지에서 정확히 $\sum_{u \in W} b_u$개를 골라 나무를 공급하게 한다. 각 마을이 어느 조선소에 나무를 보내는지는 상관없다.
  • 조선소가 지어진 마을 $i$는 한 해 동안 배를 $c_i$척 만든다.
  • 나무를 공급하는 마을은 배를 만들지 않는다.
  • 관할 아래 있는 그 밖의 마을은 총독의 관할이 없을 때와 같이 배를 $a_i$척 만든다.

통치자는 총독을 원하는 만큼 보낼 수 있다. 총독들이 최적으로 행동한다고 할 때, 모든 마을이 한 해 동안 합쳐서 만들 수 있는 배의 최대 개수를 구하라.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 5\,000$). 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 마을의 수 $n$이 주어진다 ($1 \le n \le 5000$).

다음 $n$줄에는 정수 $a_i$, $b_i$, $c_i$가 주어진다. $a_i$는 마을 $i$가 총독의 관할에 들지 않을 때 한 해 동안 만드는 배의 수이다. $b_i$는 마을 $i$에 조선소를 지을 때 나무를 공급해야 하는 다른 마을의 수이다. $c_i$는 그곳에 조선소가 지어졌을 때 마을 $i$가 한 해 동안 만드는 배의 수이다 ($1 \le a_i, c_i \le 10^9$; $1 \le b_i \le n$).

다음 $n-1$줄에는 도로로 직접 연결된 두 마을의 번호 $v_i$, $u_i$가 주어진다. 도로망이 트리임이 보장된다.

모든 테스트 케이스의 $n$ 합은 5000을 넘지 않는다.

각 테스트 케이스마다 총독을 최적으로 배치했을 때 모든 마을이 한 해 동안 합쳐서 만들 수 있는 배의 최대 개수를 한 줄에 하나씩 출력한다.