Islands

You are visiting a park with $N$ islands, numbered $1$ through $N$. From each island $i$, exactly one bridge was built, connecting island $i$ to some other island; that bridge has length $L_i$. There are therefore $N$ bridges in total. Although each bridge was built starting from one island, every bridge can be crossed in both directions. In addition, for every pair of islands there is a ferry that shuttles back and forth between them.

Because you enjoy walking more than riding ferries, you want to maximize the total length of the bridges you cross, subject to the following rules:

• You may start on any island of your choice.
• You may never visit the same island twice.
• From your current island $S$ you may move to an island $D$ that you have not visited yet, in one of two ways:
  • Walk: allowed only if a bridge directly connects $S$ and $D$. The bridge's length is added to your total walking distance.
  • Ferry: allowed only if $D$ is not reachable from $S$ using any combination of bridges and ferries you have already used. (When checking reachability, consider every path, including paths that pass through islands you have already visited.)

You do not have to visit every island, and it may be impossible to cross every bridge.

Given the $N$ bridges and their lengths, compute the maximum total distance you can walk while obeying the rules above.

• The first line contains the integer $N$, the number of islands ($2 \le N \le 1{,}000{,}000$). Islands are numbered from $1$ to $N$.
• Each of the next $N$ lines describes one bridge. Line $i$ (for $i = 1, 2, \dots, N$) contains two space-separated integers: the island at the other endpoint of the bridge built from island $i$, followed by that bridge's length $L_i$ ($1 \le L_i \le 100{,}000{,}000$). The two endpoints of every bridge are always different islands.

Print a single line containing one integer: the maximum possible total walking distance.

Note: for some inputs the answer does not fit in a 32-bit integer, so use a 64-bit integer type (for example long long in C/C++ or a normal integer in Python).

In the sample, the $N = 7$ bridges are $(1\text{-}3)$, $(2\text{-}7)$, $(3\text{-}4)$, $(4\text{-}1)$, $(5\text{-}1)$, $(6\text{-}3)$ and $(7\text{-}2)$. Note that there are two different bridges connecting islands $2$ and $7$.

One way to achieve the maximum walking distance is:

• Start on island $5$.
• Walk the bridge of length $9$ to reach island $1$.
• Walk the bridge of length $8$ to reach island $3$.
• Walk the bridge of length $4$ to reach island $6$.
• Take the ferry from island $6$ to island $7$.
• Walk the bridge of length $3$ to reach island $2$.

You finish on island $2$ with a total walking distance of $9 + 8 + 4 + 3 = 24$. The only island left unvisited is island $4$, and you can no longer reach it: not by walking (there is no bridge between island $2$ and island $4$), and not by ferry (island $4$ is reachable from island $2$ via the bridge $(2\text{-}7)$, then the ferry you already used from island $7$ to island $6$, then the bridges $(6\text{-}3)$ and $(3\text{-}4)$).