Maximum Leaves Collection in a Forest

You are given a forest consisting of one or more rooted trees. Each tree is described by the number of nodes and a set of directed edges that go from a parent to a child. Each edge carries an integer that represents the number of leaves you can collect when moving along that edge. Starting from the root (node 1) of each tree, your task is to choose a path down to any leaf so that the total number of collected leaves is maximized. Formally, for each tree, if you start at the root with a count of 0 leaves, every edge (u, v, l) adds l to your running total. When you reach a leaf, the sum of the values along the path is your collected leaves for that tree. Output the maximum collected leaves for each tree.

In mathematical terms, for each tree, if P is a path from the root to a leaf with edges carrying values (l_1, l_2, \dots, l_k), you must find a path that maximizes the sum (\sum_{i=1}^{k} l_i).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (T), the number of trees in the forest.
• For each tree, the first line contains an integer (N), the number of nodes in that tree. This is followed by (N-1) lines, each containing three space-separated integers (u), (v), and (l):
    - (u) and (v) denote the parent and child nodes, respectively (the tree is rooted at 1), and
    - (l) is the number of leaves collected when moving from (u) to (v).

outputFormat

Output a single line to standard output (stdout) containing (T) integers separated by spaces. Each integer represents the maximum number of leaves that can be collected for the corresponding tree.## sample

2
5
1 2 3
1 3 2
2 4 5
3 5 1
4
1 2 6
2 3 2
2 4 4

8 10