Minimum Initial L Value

In country H, there are N cities connected by N-1 bidirectional roads that form a tree. According to H's road law, each road has an associated positive integer cost \(w\). When travelers x and y traverse a road for the first time, their current value \(L\) decreases by \(w\); if they traverse the same road again, there is no additional decrease.

The travelers start at city 1 and plan to visit all the cities in exactly 32766 days. They are allowed to travel roads that have been used before without incurring extra cost, so that they can adjust their itinerary. However, it is required that at the end of each day the value \(L\) remains positive.

A valid route (such as an Euler tour in the tree) will traverse each road twice but incur the cost only the first time. This means that the total deduction in \(L\) during the journey is \(\sum_{e} w_e\). To ensure \(L\) remains positive after the final day, the initial \(L\) must satisfy:

[ L_{initial} - \sum_{e} w_e > 0 \quad\Longrightarrow\quad L_{initial} > \sum_{e} w_e. ]

Thus, the minimum initial \(L\) value is:

[ L_{initial} = \sum_{e} w_e + 1. ]

inputFormat

The first line contains a single integer \(N\) (the number of cities). The following \(N-1\) lines each contain three integers \(u\), \(v\), and \(w\), indicating that there is a bidirectional road between cities \(u\) and \(v\) with cost \(w\). It is guaranteed that these roads form a tree.

outputFormat

Output a single integer: the minimum initial \(L\) value required so that after deducting the cost of each road on its first traversal, the value remains positive at the end of every day.

sample

2
1 2 5

6