Maximum Weight Simple Path in a Tree

You are given an undirected tree with n nodes and n-1 weighted edges. Each edge is represented by three integers u, v and w, which indicates an edge between nodes u and v with weight w.

Your task is to find the weight of the maximum weighted simple path in the tree, i.e. the diameter of the tree.

The diameter of a tree can be computed by selecting an arbitrary node, finding the farthest node from it, and then finding the farthest node from that node. Formally, if we denote the distance between two nodes u and v as \(d(u,v)\), the answer is:

\( \max_{u,v \in V} d(u,v) \)

inputFormat

The input is given as follows:

1. The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes in the tree.
2. If n > 1, the next n-1 lines each contain three integers u, v and w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁹), representing an edge between node u and node v with weight w.

outputFormat

Output a single integer, the maximum weight of a simple path in the tree.

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

13