## An Animal Contest 1 P5 - Odd Alpacas

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem type

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?

#### 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 .

#### Sample Input 2

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

#### Sample Output 2

1