408009 - 岛屿

你准备浏览一个公园，公园由 N 个岛屿组成。管理部门从每个岛屿 i 出发，向另一个岛屿建了一座长度为 Li 的桥（桥可双向行走）；同时每对岛屿之间都有一艘专用渡船。相比乘船，你更喜欢步行，希望走过的桥的总长度尽可能长，但受到以下限制： 1．可自行挑选一个岛开始游览。 2．任何一个岛都不能游览一次以上。 3．任何时间都可以从当前岛 S 去另一个从未到过的岛 D，有如下方法： （1）步行：仅当两岛之间有桥时可行，桥长累加到步行总距离。 （2）渡船：仅当没有任何桥和以前使用过的渡船的组合可由 S 走到 D 时才可选择（检查可达性时考虑所有路径，包括经过已游览过的岛）。 注意：不必游览所有岛，也可能无法走完所有桥。

第一行一个整数 N（2 ≤ N ≤ 10^6），表示岛屿数目。 随后 N 行，第 i 行两个整数，表示由岛 i 筑的桥：第一个整数为桥另一端的岛，第二个整数为桥的长度 Li（1 ≤ Li ≤ 108）。每座桥两端总是位于不同岛上。

仅一个整数，即可能的最大步行距离。

7 座桥分别为 (1-3)、(2-7)、(3-4)、(4-1)、(5-1)、(6-3)、(7-2)。注意岛 2 与岛 7 之间有两座不同的桥。 一种最优游览方法： 1．由岛 5 开始。 2．步行长度 9 的桥到岛 1。 3．步行长度 8 的桥到岛 3。 4．步行长度 4 的桥到岛 6。 5．搭渡船由岛 6 到岛 7。 6．步行长度 3 的桥到岛 2。 总步行距离 = 9 + 8 + 4 + 3 = 24。只有岛 4 没有去。 结束时不能再游览岛 4 的原因： 1．不能步行去：岛 2 与岛 4 之间无桥。 2．不能搭渡船去：可由当前岛 2 到达岛 4（走 (2-7) 桥，再搭曾搭过的渡船由岛 7 去岛 6，走 (6-3) 桥，最后走 (3-4) 桥）。