Furthest Apart Vertices in a Weighted Tree

Given a weighted tree with \(n\) vertices and \(n-1\) edges, find two vertices that are the furthest apart. The distance between two vertices is defined as the sum of the weights of the edges on the unique path connecting them. This maximum distance is known as the diameter of the tree.

Formally, for vertices \(u\) and \(v\), let \(d(u,v)\) represent the distance between them. You are required to determine two vertices \(a\) and \(b\) such that \(d(a,b)\) is maximized.

Note: If multiple solutions exist, output any valid pair.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) ((n \ge 2)), the number of vertices in the tree. This is followed by (n-1) lines, each containing three space-separated integers (u), (v), and (w), which represent an edge between vertices (u) and (v) with weight (w).

outputFormat

Output via standard output (stdout) two integers separated by a space representing the two vertices that are furthest apart in the tree. If there are multiple correct answers, any valid pair is acceptable.## sample

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

5 3