D. Cow the Tree Nerd
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A beautiful path of a weighted tree is a simple path that visits at least $$$2$$$ nodes, in which the edges it visits have alternating signs. Its cost is the sum of the weights of the edges it visits. A best path is a beautiful path with the maximum cost among all other beautiful paths in the tree.

Spyrosaliv had a weighted tree of size $$$n$$$, and he tried finding the cost of the best path. However, Cow the Cow, nerdy as he is, thought the problem was far too easy.

Therefore, he asked the following question: "In one operation, you can choose any two edges and swap their weights. What is the maximum possible cost of the best path after a finite number of such operations?"

Cow the Cow easily solved the problem, but Spyrosaliv struggled. Can you help Spyrosaliv solve this problem?

Input

The first line contains one integer, $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$.

In the $$$i$$$-$$$th$$$ of the next $$$n-1$$$ lines, there are three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ $$$(-10^9 \le w_i \le 10^9, w_i \neq 0)$$$, denoting an edge $$$(u_i, v_i)$$$ in the tree with weight $$$w_i$$$.

The input is guaranteed to provide a valid tree.

Output

Output one integer, the maximum possible cost of the best path after a finite number of swaps.

Examples
Input
6
1 2 3
2 3 -1
3 4 2
4 5 -1
4 6 -130
Output
4
Input
5
1 2 8
2 3 -1
3 4 -100
4 5 10
Output
17
Input
2
1 2 -10
Output
-10
Input
3
1 2 100
1 3 150
Output
150
Note

For the first example, see the following tree:

The path that visits nodes $$$1, 2, 3$$$ in that order is beautiful with cost $$$2$$$, but the path $$$6, 4, 5$$$ is not, since two consecutive edges have weights with the same sign.

The best path is the path that visits nodes $$$1, 2, 3, 4$$$ in that order, since it is a beautiful path with the maximal cost of $$$4$$$.

In the second example, it is optimal to swap the weights of edges $$$(3, 4)$$$ and $$$(4, 5)$$$ in one operation. Then, the cost of the best path is $$$17$$$. It can be shown that $$$17$$$ is the maximal possible cost of the best path among all possible combinations of operations.

In the third example, there is exactly one beautiful path, which visits nodes $$$1$$$ and $$$2$$$; therefore, it is the best path with cost $$$-10$$$.