Merchant

The cities of Byteland are joined by roads so that between any two cities there is exactly one route, whether direct or passing through other cities. In other words, the road network forms a tree.

A merchant comes to Byteland to make money. He first settles in one city (the starting city) and then travels to another city of his choice (the ending city). Byteland's law forbids him from entering the same city twice along the way, so his route is the unique simple path between the two cities.

Each road has a known value: travelling it, the merchant gains that many bytalars, and a negative value means a loss. His total profit is the sum of the values of all roads on his route. Choose the starting and ending city so that this total profit is as large as possible. The two cities may be the same, in which case the merchant travels no road and his profit is 0.

The first line contains one integer $n$ ($2 \le n \le 10^6$), the number of cities, numbered from $1$ to $n$.

Each of the next $n - 1$ lines contains three integers $a$, $b$ and $x$ ($-10^9 \le x \le 10^9$), meaning there is a direct road between cities $a$ and $b$ on which the merchant gains $x$ bytalars (a negative $x$ is a loss).

Print a single integer: the largest total profit the merchant can earn.