The cows hate calisthenics (exercises). They do, however, enjoy jogging a little bit. They have surveyed their pasture and have created a list of all the possible paths in the field. Interestingly, the paths are "directed" -- paths can be traversed only in one direction. Sometimes, two different paths connect a pair of points, one path going one way and one path going the other way.

Your job is to help the cows find the shortest "circular route" around which they can jog. A circular route is one which starts and ends at the same location. The length of a route is the sum of the lengths of the paths one must traverse to jog around the route.

Paths in their pasture always connect two points. Each point is named as a positive integer. These points are sequentially numbered, starting at 1. Distances between points are positive integers.

It is guaranteed that at least one "circular route" appears in any supplied cow pasture.

Input

• Line $1$: $N$ ($1 \le N \le 2000$), the number of directed paths; at most 400 distinct points occur.
• Lines $2..N+1$: Each line gives the beginning point, ending point, and distance (at most 1000) of one path.

Output

A single line with the integer distance around the shortest possible circuit.

Examples

Input 1

4
3 1 5
1 2 4
2 3 3
1 3 44

Output 1

12

Problem credits: Hal Burch & Russ Cox