Following the recent healthcare expenditures related to the SPLAY-CRT-2 virus, the treasury of Bajtograd, the capital of Bajtocja, is empty. In exactly four days, the money will run out, and the city will be cut off from electricity. It is hard to even imagine the chaos that would ensue in such a situation – this must not be allowed to happen! A new tax must be introduced as quickly as possible to patch the budget hole.

Bajtograd consists of $n$ roundabouts numbered from $1$ to $n$ and $n - 1$ streets connecting them. It is possible to reach any roundabout from any other using the streets. In particular, some roundabouts are connected to only one street (it is not hard to guess why the city treasury is empty with such mismanagement).

Bajtocjans live along every street, ready to give their money to save the city. For each street, a potential profit from collecting taxes on it has been estimated. This profit may be negative on some streets, as various costs of tax collection have already been deducted from it – for example, those related to equipment and the tax collector's fee.

Each hired tax collector will start work at one roundabout and will collect taxes for the next four days. For one day, they are able to collect taxes along one of the streets, moving from one end to the other. Each subsequent day, the collector will collect taxes on one of the remaining streets connected to the roundabout where they finished their work the previous day. The financial situation is dire, so the collectors must work for four days without a break! Therefore, each employee will collect taxes during this time from exactly four streets located on a path between two certain roundabouts in Bajtograd. Additionally, to avoid social unrest, it has been ordered that no tax can be collected from any street more than once.

Help the authorities of Bajtograd and calculate the maximum amount of money that can be raised from taxes in this way.

Input

The first line of input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$), representing the number of roundabouts in Bajtograd. Each of the next $n-1$ lines contains descriptions of individual streets; the $i$-th of them contains three integers $u_i, v_i, z_i$ ($1 \le u_i, v_i \le n, -10^9 \le z_i \le 10^9$), meaning that roundabouts $u_i$ and $v_i$ are connected by a street, from which collecting taxes will yield a profit of $z_i$ bajtalars.

Output

In the single line of output, print one integer – the maximum profit from taxes expressed in bajtalars.

Examples

Input 1

19
1 2 1
2 3 2
3 4 -1
4 5 -1
5 6 2
6 7 11
7 8 12
8 9 13
9 10 14
11 12 3
12 13 0
13 14 0
14 15 0
15 16 1
16 4 0
4 17 0
17 18 0
18 19 2

Output 1

57

Input 2

6
1 2 2
2 3 -1
3 4 -1
4 5 -1
5 6 2

Output 2

0

Note

Explanation of the examples: In the first test case, in the optimal strategy, we hire 4 tax collectors who will follow the routes: between roundabouts 2 and 6, gaining 2 bajtalars; between roundabouts 6 and 10, gaining 50 bajtalars; between roundabouts 11 and 15, gaining 3 bajtalars; between roundabouts 16 and 19, gaining 2 bajtalars.

In the second case, each of the potential tax collector routes would result in losses. Therefore, it is not profitable to hire anyone.