Maximum Sum of Three Connected Edges in a Tree

You are given a tree with n nodes and n-1 edges. Each edge has an associated positive integer weight. Your task is to choose exactly 3 edges from the tree such that if you take all the endpoints of these edges, then using only the chosen edges, every pair of endpoints is reachable. In other words, the subgraph induced by the chosen edges must be connected. Since the tree is acyclic, a connected subgraph with three edges will always be a tree on 4 nodes, which can have either a star (one vertex connected to three others) or a chain (a simple path of four vertices) structure.

Your goal is to maximize the total sum of weights of the selected three edges.

Notes:

• If the tree does not have enough nodes to form a connected subgraph with 3 edges (i.e. when n < 4), you may assume that the input will satisfy n ≥ 4.
• The tree is given as 1-indexed nodes.
• You need to consider two possible configurations:
  • Star configuration: choose three edges sharing a common vertex. For every vertex with degree at least 3, consider the sum of the top three incident edge weights.
  • Chain configuration: consider a chain of 4 nodes (u-v-w-x). For an edge (v, w) chosen as the middle edge, try to extend on both sides with the best (largest weight) edge from v (excluding the edge to w) and from w (excluding the edge to v). The candidate sum is the weight of the middle edge plus these two additional weights.
• The answer is the maximum sum achieved by either configuration.

inputFormat

The first line contains an integer n (n ≥ 4), representing the number of nodes in the tree.

Each of the following n-1 lines contains three integers u, v, and w indicating that there is an edge between nodes u and v with weight w (a positive integer).

outputFormat

Output a single integer — the maximum possible sum of the weights of the selected three edges that form a connected subgraph.

sample

4
1 2 3
1 3 5
1 4 4

12