17712번 - Telegraph 서브태스크다국어

JOI 諸島は太平洋に浮かぶ小さな島国である．JOI 諸島には N 個の島があり，1 から N までの番号が付 けられている．

JOI 諸島では島同士の通信は主に無線によって行われる．それぞれの島には電波の送信機と受信機がひ とつずつある．送信機は全方向に電波を送ることができるが，受信機は特定の方向からの電波しか受け取 ることができない．そのため，それぞれの受信機は，特定のひとつの島からの電波しか受け取ることがで きない．ただし，受信機の向きを変えることで，どの島からの電波を受け取ることができるかを変えるこ とができる．

現在，島 i (1 ≦ i ≦ N) の受信機は島 A_i (Ai ≠ i) からの電波を受け取ることができる．また，島 i の受信 機の向きを変えるのにかかるコストは，どう向きを変えるかによらず， Ci である．

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)．