Maximum Weight Path in a Tree

You are given a tree with n nodes, where the tree is rooted at node 1. Each edge in the tree has an associated weight. Your task is to find the maximum sum of weights along any simple path that starts at the root (node 1) and ends at any leaf node. Formally, if you denote a path from node 1 to a leaf as \(1 \to v_1 \to v_2 \to \cdots \to v_k\), you need to maximize the sum \(w(1, v_1) + w(v_1, v_2) + \cdots + w(v_{k-1}, v_k)\).

Input format: The first line contains an integer t representing the number of test cases. For each test case, the first line contains an integer n — the number of nodes in the tree. Then follow n-1 lines, each containing three integers u, v, and w describing an edge between nodes u and v with weight w.

Output format: For each test case, output the maximum weight path from the root to any leaf on a separate line.

inputFormat

The input consists of multiple test cases.

• The first line contains an integer t, the number of test cases.
• For each test case:
• The first line contains an integer n (the number of nodes in the tree).
• The next n-1 lines each contain three space-separated integers u v w representing an edge between node u and node v with weight w.

outputFormat

For each test case, print a single integer on a new line representing the maximum weight sum along a valid path from the root (node 1) to any leaf node.

## sample

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

5
3
2

</p>