It is a well-known fact that alpacas love numbers. The reason behind this fascination is uncertain, but that shouldn't be your concern at the moment. You've stumbled upon a herd of alpacas living in $N$ connected villages, joined by $N-1$ bidirectional roads of length $w_i$.

Let us define $x$ as the number of even length pathways between any two villages and $y$ as the number of odd length pathways between any two villages. The length of a pathway between $u_i$ and $v_i$ is defined as the sum of the road lengths connecting $u_i$ and $v_i$.

You look up and find yourself face to face with the queen alpaca and she's angry. She orders you to tell her the minimum value of $|x-y|$ given that you can change the length of at most $1$ road. Fail to do so and you'll be turned into an alpaca. Can you make it out alive?

Constraints

$1\le N\le 2\cdot {10}^5$

$1\le w_i\le {10}^4$

$1\le u_i,v_i\le N$

Subtask 1 [10%]

$1\le N\le 200$

Subtask 2 [20%]

$1\le N\le 2\cdot {10}^3$

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line of input will contain the integer $N$, the number of villages.

The next $N-1$ lines will contain the integers $u_i$, $v_i$, and $w_i$, representing a bidirectional road between $u_i$ and $v_i$ that is $w_i$ units long.

Output Specification

Output the minimal possible value of $|x-y|$ after modifying the length of at most one edge.

Note that 64-bit integers may be required.

Sample Input 1

5
5 3 97
4 2 21
1 2 49
3 2 4

Sample Output 1

2

Explanation for Sample Output 1

An optimal solution is not changing any lengths.

In the original graph, there are $6$ pairs of villages which form a path of odd length:

• $(1,2)$ of length $49$.
• $(1,3)$ of length $53$.
• $(2,4)$ of length $21$.
• $(2,5)$ of length $101$.
• $(3,4)$ of length $25$.
• $(3,5)$ of length $97$.

Furthermore, there are $4$ pairs of villages which form a path of even length.

• $(1,4)$ of length $70$.
• $(1,5)$ of length $150$.
• $(2,3)$ of length $4$.
• $(4,5)$ of length $122$.

Thus, the answer is $|6-4|=2$.

Sample Input 2

6
6 1 100
2 1 86
4 3 12
3 2 40
5 2 44

Sample Output 2

1