Maximum Travel Distance on a Tree

Given a tree with \(n\) nodes numbered from 1 to \(n\) and \(n-1\) edges, where each edge connects two nodes \(u\) and \(v\) with an associated weight \(w\), compute the maximum travel distance starting from node 1. The travel distance is defined as the sum of the weights along a path, and you are allowed to traverse each edge only once since the graph is a tree.

The mathematical formulation is: \(\text{Distance} = \sum_{edge \in path}w\). The objective is to identify the path which yields the maximum distance starting from node 1.

Note: The tree is undirected. If there is only a single node, the result is 0.

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the tree. The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\) indicating an edge between node \(u\) and node \(v\) with a weight of \(w\).

Input is provided via standard input (stdin).

outputFormat

Output a single integer which is the maximum travel distance starting from node 1. The result should be written to standard output (stdout).

3
1 2 2
1 3 3

3