Speedrunning can be interesting.

Leon is speedrunning a video game, intending to reach all of the possible endings.

The entire game can be mapped out as a rooted tree of ~N~ checkpoints connected by one-way routes. Route ~i~ connects checkpoint ~u_i~ to ~v_i~, and playing through this route takes exactly ~t_i~ seconds. Let checkpoint ~1~ represent the beginning of the game; all other checkpoints are reachable through some set of particular routes.

Note that a checkpoint that branches off into multiple other checkpoints represents a point in the game where Leon must make a key decision that will alter the course of the game. Furthermore, a checkpoint that leads to nowhere else (a dead-end) represents an ending.

The game also features a built-in save/load mechanic. Leon is allowed to save the game only at checkpoints, which keeps track of his current point in the game. He may choose to load the save file at any time, immediately bringing him back to the saved checkpoint. Additionally, he also has the power to reset the game at any time, which instantly takes him all the way back to the beginning (checkpoint ~1~).

This save/load mechanic would have made his play-through a lot easier if it weren't for the game's inconsiderate developers - only providing one save slot. If Leon plays the game optimally, what would the minimum time taken to complete the game (i.e. visit all the checkpoints) be?

Constraints

~1 \le u_i < v_i \le N~

~1 \le t_i \le 10^9~

Subtask	Percentage	Additional Constraints
~1~	~10~	~2 \le N \le 7~
~2~	~20~	~2 \le N \le 12~
~3~	~30~	~2 \le N \le 80~
~4~	~40~	~2 \le N \le 5000~

Input Specification

The first line contains integer ~N~: the number of checkpoints in the game.

The following ~N-1~ lines each contain three integers: ~u_i~, ~v_i~, and ~t_i~. This represents a one-way route taking ~t_i~ seconds to play from checkpoint ~u_i~ to ~v_i~.

Output Specification

A single integer: the minimum amount of time required to complete the entire game.

Sample Input 1

7
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1

Sample Output 1

6

Sample Input 2

15
1 2 2
1 3 1
2 4 1
2 5 1
3 6 2
3 7 2
4 8 2
4 9 2
5 10 2
5 11 2
6 12 1
6 13 1
7 14 1
7 15 1

Sample Output 2

23