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