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 connected villages, joined by bidirectional roads of length .

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

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 given that you can change the length of **at most** road. Fail to do so and you'll be turned into an alpaca. Can you make it out alive?

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [20%]

##### Subtask 3 [70%]

No further constraints.

#### Input Specification

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

The next lines will contain the integers , , and , representing a bidirectional road between and that is units long.

#### Output Specification

Output the minimal possible value of 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 pairs of villages which form a path of **odd** length:

- of length .
- of length .
- of length .
- of length .
- of length .
- of length .

Furthermore there are pairs of villages which form a path of **even** length.

- of length .
- of length .
- of length .
- of length .

Thus, the answer is .

#### Sample Input 2

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

#### Sample Output 2

`1`

## Comments