Maximum Path Strength in a Tree

You are given a tree with n vertices and n-1 edges. Each edge is associated with a positive weight. The path strength is defined as the sum of the weights along a path between two vertices. Your task is to compute the maximum path strength in the tree, which is equivalent to finding the diameter of the tree.

Hint: One common strategy is to perform two breadth-first searches (BFS). The first BFS starts from an arbitrary vertex and finds the farthest vertex from it. Then, a second BFS starting from that farthest vertex gives the distance to the farthest vertex from it, which is the answer. Mathematically, if the tree is denoted by \(T=(V,E)\), you are asked to compute:

[ \max_{u,v \in V} ; \sum_{e \in P(u,v)} w(e) ]

inputFormat

The input is given from stdin in the following format:

n
u1 v1 w1
u2 v2 w2
... (n-1 lines total, if n > 1)

The first line contains a single integer n (\(1 \le n \le 10^5\)). Each of the following n-1 lines contains three integers \(u, v, w\) (\(1 \le u,v \le n\), \(1 \le w \le 10^9\)), which indicate an edge between vertices \(u\) and \(v\) with weight \(w\). If n is 1, the tree has no edges.

outputFormat

Output the maximum path strength of the tree to stdout.

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

10