Maximum Distance Between Cities

You are given a tree representing a network of cities. The tree has n nodes (cities) and n - 1 edges (roads), ensuring that there is a unique path between any two cities. Each road is described by three integers u, v, and d which represent a bidirectional road connecting city u and city v with length d.

Your task is to compute the diameter of the tree, which is defined as the maximum distance between any two cities. Mathematically, if we denote the distance between two cities i and j as \(dist(i,j)\), you need to find: \[ \max_{1 \leq i,j \leq n} \; dist(i,j) \]

This problem can be solved by performing two breadth-first searches (BFS). First, perform a BFS starting from any arbitrary city (for instance, city 1) to find the furthest city. Then, perform another BFS starting from that furthest city to determine the longest distance in the tree.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n representing the number of cities.
• The following n - 1 lines each contain three integers u, v, and d indicating that there is a road between cities u and v with distance d.

outputFormat

Output a single integer to standard output (stdout): the maximum distance between any two cities in the network.

4
1 2 4
2 3 3
3 4 5

12