전보

JOI 제도는 태평양에 떠 있는 작은 섬나라이다. JOI 제도에는 N개의 섬이 있고, 1부터 N까지 번호가 붙어 있다.

JOI 제도에서 섬 사이의 통신은 주로 무선으로 이루어진다. 각 섬에는 전파의 송신기와 수신기가 하나씩 있다. 송신기는 모든 방향으로 전파를 보낼 수 있지만, 수신기는 특정한 방향에서 오는 전파만 받을 수 있다. 그래서 각 수신기는 특정한 한 섬에서 오는 전파만 받을 수 있다. 다만 수신기의 방향을 바꾸면 어느 섬에서 오는 전파를 받을지 바꿀 수 있다.

현재 섬 i (1 ≤ i ≤ N)의 수신기는 섬 A_i (A_i ≠ i)에서 오는 전파를 받을 수 있다. 또 섬 i의 수신기 방향을 바꾸는 데 드는 비용은 어떻게 바꾸든 C_i이다.

JOI 제도에서는 공공사업으로 전보 서비스를 하고 있다. 섬 i (1 ≤ i ≤ N)에서 보낸 전파를 섬 j (1 ≤ j ≤ N, j ≠ i)의 수신기가 받을 수 있을 때, 섬 i에서 섬 j로 무선 통신으로 전보를 보낼 수 있다. 또 전보는 여러 섬을 거쳐 보내도 된다. 즉 섬 i, j, k (1 ≤ i, j, k ≤ N이고 i, j, k는 각각 다르다)에 대해 섬 i에서 섬 j로 전보를 보낼 수 있고 섬 j에서 섬 k로 전보를 보낼 수 있을 때, 섬 i에서 섬 k로 전보를 보낼 수 있다. 무선 통신 외의 방법으로 전보를 보낼 수는 없다.

JOI 제도의 체신대신인 당신은 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있게 하고 싶다. 그러기 위해서는 몇몇 섬의 수신기 방향을 바꿔야 할 수도 있다. 몇몇 섬의 수신기 방향을 바꾸는 데 드는 비용은 각 수신기의 방향을 바꾸는 데 드는 비용의 총합이다.

임의의 섬에서 임의의 섬으로 전보를 보낼 수 있게 하는 데 드는 비용의 최솟값을 계산하라.

JOI 제도의 섬의 수와 각 섬의 수신기에 대한 정보가 주어졌을 때, 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있게 하는 데 드는 비용의 최솟값을 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 1번째 줄에는 정수 N이 쓰여 있다. 이것은 JOI 제도에 N개의 섬이 있음을 나타낸다.
• 이어지는 N개의 줄 중 i번째 줄 (1 ≤ i ≤ N)에는 정수 A_i, C_i가 공백을 구분으로 쓰여 있다. 이것은 섬 i의 수신기가 현재 섬 A_i에서 오는 전파를 받을 수 있고, 방향을 바꾸는 데 드는 비용이 C_i임을 나타낸다.

표준 출력에 임의의 섬에서 임의의 섬으로 전보를 보낼 수 있게 하는 데 드는 비용의 최솟값을 1줄로 출력하라.

• 2 ≤ N ≤ 100 000.
• 1 ≤ A_i ≤ N (1 ≤ i ≤ N).
• A_i ≠ i (1 ≤ i ≤ N).
• 1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ N).