Maximizing Travel Fees in T Kingdom

In the glorious T Kingdom, the capital is connected to all major cities via a network of express roads. To save expenses, the ministers designed a remarkable plan so that every major city can be reached from the capital directly or indirectly by a unique simple path (i.e. without revisiting any city).

J, an important minister, travels nonstop from one city to another. During his continuous journey, his road fee is determined by the distance he covers. Specifically, for the kilometer between the \(x-1\)-th and the \(x\)-th kilometer (where \(x\) is a positive integer), he pays \(x+10\) units. For example, traveling 1 kilometer costs \(11\) units and 2 kilometers cost \(11+12=23\) units.

The fee for a journey covering \(d\) kilometers is therefore given by:

\[ \text{fee} = \frac{d^2 + 21d}{2} \]

Your task is to determine the maximum fee that J might pay among all possible journeys in the T Kingdom, where a journey is defined as traveling along the unique simple path between any two distinct cities in the road network (which forms a tree).

inputFormat

The first line contains an integer \(n\) (\(2 \leq n \leq 10^5\)), representing the number of cities.

Then \(n-1\) lines follow. Each line contains three integers \(u\), \(v\), and \(w\) (\(1 \leq u,v \leq n\), \(1 \leq w \leq 10^4\)), indicating there is a road connecting cities \(u\) and \(v\) with a length of \(w\) kilometers.

outputFormat

Output a single integer, the maximum possible road fee (in cost units) among all journeys between two distinct cities.

sample

2
1 2 1

11