Longest Path Between Leaves in a Tree

You are given a weighted tree with n nodes. A tree is an acyclic connected graph. Each edge has an associated weight. The task is to compute the longest path between any two leaves of the tree, which is also known as the tree diameter. In a tree, the diameter is defined as \(L = \max_{u,v \in \text{leaves}} d(u,v)\), where \(d(u,v)\) is the sum of weights on the unique path from node \(u\) to node \(v\).

If the tree has only one node, output 0. Otherwise, use a two-phase depth-first search (DFS) algorithm: first, pick an arbitrary node and find the farthest node from it; then, from that farthest node, find the farthest node again. The distance between these two nodes is the answer.

inputFormat

The input is provided via standard input (stdin). The first number is an integer (n) ((n \ge 1)) that represents the number of nodes in the tree. Following this, there are (n-1) groups of three integers each: (u), (v), and (w), representing an edge between nodes (u) and (v) with weight (w).

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest path between any two leaves in the tree.## sample

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

15