Diameter of a Tree in a Magical Land

You are given a magical land with n villages and n-1 bidirectional roads connecting them, forming a tree. Each road has an associated travel time. The diameter of the tree is defined as the longest distance between any two villages.

Mathematically, if \(d(u,v)\) denotes the travel time between villages \(u\) and \(v\), then the diameter of the tree is:

\(\max_{1 \le u,v \le n} d(u,v)\)

Your task is to compute the diameter given the number of villages and the list of roads.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer \(n\) representing the number of villages.
• Each of the following \(n-1\) lines contains three space-separated integers \(u\), \(v\), and \(w\). This denotes that there is a road between village \(u\) and village \(v\) with a travel time of \(w\).

outputFormat

Output a single integer to standard output (stdout) representing the diameter of the tree, i.e. the longest travel time between any two villages.

3
1 2 3
1 3 4

7