섬 (Islands)

$N$개의 섬이 있는 공원을 방문한다. 섬에는 $1$번부터 $N$번까지 번호가 매겨져 있다. 각 섬 $i$에서는 정확히 하나의 다리가 놓여 있으며, 이 다리는 섬 $i$를 다른 어떤 섬과 잇고 그 길이는 $L_i$이다. 따라서 다리는 모두 합쳐 $N$개이다. 각 다리는 한 섬에서 시작해 놓였지만, 지금은 모든 다리를 양방향으로 건널 수 있다. 또한 모든 섬 쌍 사이에는 두 섬을 오가는 여객선이 하나씩 있다.

여객선을 타는 것보다 걷는 것을 좋아하므로, 아래 규칙을 지키면서 건너는 다리 길이의 합을 최대로 만들고 싶다.

• 원하는 섬에서 출발할 수 있다.
• 같은 섬을 두 번 방문할 수 없다.
• 현재 있는 섬 $S$에서 아직 방문하지 않은 섬 $D$로, 다음 두 가지 방법 중 하나로 이동할 수 있다.
  • 걷기: $S$와 $D$를 직접 잇는 다리가 있을 때만 가능하다. 그 다리의 길이가 총 걸은 거리에 더해진다.
  • 여객선: 이미 사용한 다리와 여객선을 어떤 방식으로 조합하더라도 $S$에서 $D$에 도달할 수 없을 때만 가능하다. (도달 가능 여부를 판단할 때는, 이미 방문한 섬을 지나는 경로를 포함해 모든 경로를 고려한다.)

모든 섬을 방문할 필요는 없으며, 모든 다리를 건너는 것이 불가능할 수도 있다.

$N$개의 다리와 각 길이가 주어졌을 때, 위 규칙을 지키며 걸을 수 있는 최대 거리를 구하는 프로그램을 작성하라.

• 첫째 줄에 섬의 개수 $N$이 주어진다 ($2 \le N \le 1{,}000{,}000$). 섬은 $1$번부터 $N$번까지 번호가 매겨져 있다.
• 다음 $N$개의 줄에는 각각 하나의 다리가 설명된다. $i$번째 줄($i = 1, 2, \dots, N$)에는 두 정수가 공백으로 구분되어 주어지며, 첫 번째 정수는 섬 $i$에서 놓인 다리의 반대쪽 끝에 있는 섬의 번호, 두 번째 정수는 그 다리의 길이 $L_i$이다 ($1 \le L_i \le 100{,}000{,}000$). 모든 다리의 두 끝점은 항상 서로 다른 섬이다.

걸을 수 있는 최대 거리를 한 정수로 한 줄에 출력한다.

참고: 일부 입력에서는 답이 32비트 정수 범위를 넘을 수 있으므로 64비트 정수 자료형을 사용해야 한다 (예: C/C++의 long long, Python은 기본 정수로 충분하다).

예시에서 $N = 7$개의 다리는 $(1\text{-}3)$, $(2\text{-}7)$, $(3\text{-}4)$, $(4\text{-}1)$, $(5\text{-}1)$, $(6\text{-}3)$, $(7\text{-}2)$이다. 섬 $2$와 섬 $7$을 잇는 서로 다른 다리가 두 개 있음에 유의한다.

최대 걷기 거리를 얻는 한 가지 방법은 다음과 같다.

• 섬 $5$에서 출발한다.
• 길이 $9$인 다리를 걸어 섬 $1$에 도착한다.
• 길이 $8$인 다리를 걸어 섬 $3$에 도착한다.
• 길이 $4$인 다리를 걸어 섬 $6$에 도착한다.
• 섬 $6$에서 섬 $7$로 여객선을 탄다.
• 길이 $3$인 다리를 걸어 섬 $2$에 도착한다.

마지막에는 섬 $2$에 있고, 걸은 거리의 합은 $9 + 8 + 4 + 3 = 24$이다. 방문하지 못한 섬은 섬 $4$뿐이며, 더 이상 그곳에 갈 수 없다. 걸어서 갈 수 없는 이유는 섬 $2$와 섬 $4$를 잇는 다리가 없기 때문이고, 여객선으로 갈 수 없는 이유는 섬 $2$에서 다리 $(2\text{-}7)$, 이미 사용한 섬 $7$→섬 $6$ 여객선, 그리고 다리 $(6\text{-}3)$와 $(3\text{-}4)$를 거쳐 섬 $4$에 도달할 수 있기 때문이다.