Maximum Tree Cumulative Degree

In many ancient mythologies trees play an intimate role. In this problem we explore a special tree property called the cumulative degree. Consider an undirected tree with n nodes. Each edge in the tree is assigned a positive capacity. A node of degree 1 (i.e. a leaf) is called a terminal node.

For any node \(x\), define its cumulative degree \(A(x)\) as the maximum total flow that can be sent from \(x\) to all other terminal nodes simultaneously, subject to the following rules:

• Each edge can carry flow up to its capacity.
• For each simple path from \(x\) to a terminal node, the flow that can be sent along that path is limited by the minimum capacity among its constituent edges.
• If an internal node is used to distribute flow to more than one branch, the flows are computed independently (since the tree branches do not share edges once separated by the source).

More formally, for a chosen source node \(x\), for every neighbour \(v\) of \(x\), let

[ f(v,x)=\begin{cases} \infty, & \text{if } v \text{ is a terminal node when the edge to } x \text{ is removed};\ \sum_{w\in adj(v)\setminus{x}} \min\big( c(v,w), f(w,v)\big), & \text{otherwise}, \end{cases} ]

and define

[ A(x)=\sum_{v\in adj(x)} \min\big(c(x,v), f(v,x)\big). ]

The cumulative degree of the tree is defined as

[ \max_{x} A(x). ]

Your task is to compute the cumulative degree of the given tree.

inputFormat

The first line contains a single integer n (\(1\le n\le 10^5\)) representing the number of nodes in the tree.

Each of the following n-1 lines contains three integers \(u\), \(v\), and \(c\) (\(1\le u,v\le n, 1\le c\le 10^9\)), representing an edge between nodes \(u\) and \(v\) with capacity c.

It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer — the cumulative degree of the tree, i.e. the maximum \(A(x)\) over all nodes \(x\).

sample

2
1 2 10

10