หมู่เกาะ JOI เป็นประเทศเกาะขนาดเล็กในมหาสมุทรแปซิฟิก มีเกาะ $N$ เกาะ หมายเลขตั้งแต่ $1$ ถึง $N$

การสื่อสารระหว่างเกาะในหมู่เกาะ JOI ใช้คลื่นวิทยุเป็นหลัก แต่ละเกาะมีเครื่องส่งและเครื่องรับอย่างละหนึ่งเครื่อง เครื่องส่งสามารถส่งคลื่นได้ทุกทิศทาง แต่เครื่องรับรับคลื่นได้จากทิศทางที่กำหนดเท่านั้น ดังนั้นเครื่องรับแต่ละเครื่องจึงรับคลื่นได้จากเกาะใดเกาะหนึ่งเท่านั้น อย่างไรก็ตาม สามารถเปลี่ยนเกาะที่รับคลื่นได้ด้วยการเปลี่ยนทิศทางของเครื่องรับ

ปัจจุบันเครื่องรับบนเกาะ $i$ ($1 \le i \le N$) รับคลื่นจากเกาะ $A_i$ ($A_i \ne i$) ได้ ค่าใช้จ่ายในการเปลี่ยนทิศทางเครื่องรับบนเกาะ $i$ เท่ากับ $C_i$ ไม่ว่าจะเปลี่ยนไปในทิศทางใด

หมู่เกาะ JOI ให้บริการโทรเลขเป็นบริการสาธารณะ เมื่อเครื่องรับบนเกาะ $j$ ($1 \le j \le N$, $j \ne i$) รับคลื่นจากเกาะ $i$ ($1 \le i \le N$) ได้ ก็สามารถส่งโทรเลขจากเกาะ $i$ ไปยังเกาะ $j$ ผ่านคลื่นวิทยุได้ นอกจากนี้ยังสามารถส่งโทรเลขผ่านเกาะอื่นหลายเกาะได้ กล่าวคือ สำหรับเกาะ $i,j,k$ ($1 \le i,j,k \le N$ และทั้งสามเกาะแตกต่างกัน) หากส่งโทรเลขจากเกาะ $i$ ไปเกาะ $j$ และจากเกาะ $j$ ไปเกาะ $k$ ได้ ก็สามารถส่งโทรเลขจากเกาะ $i$ ไปเกาะ $k$ ได้ ไม่สามารถส่งโทรเลขด้วยวิธีอื่นนอกจากคลื่นวิทยุ

คุณเป็นรัฐมนตรีว่าการกระทรวงการสื่อสารของหมู่เกาะ JOI และต้องการให้ส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้ เพื่อให้เป็นเช่นนั้น อาจต้องเปลี่ยนทิศทางเครื่องรับบนบางเกาะ ค่าใช้จ่ายในการเปลี่ยนทิศทางเครื่องรับหลายเครื่องคือผลรวมของค่าใช้จ่ายในการเปลี่ยนทิศทางของแต่ละเครื่อง

จงคำนวณค่าใช้จ่ายต่ำสุดที่ทำให้ส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้

ภารกิจ

เมื่อกำหนดจำนวนเกาะของหมู่เกาะ JOI และข้อมูลเครื่องรับบนแต่ละเกาะ จงเขียนโปรแกรมหาค่าใช้จ่ายต่ำสุดที่ทำให้ส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N$ หมายความว่าหมู่เกาะ JOI มีเกาะ $N$ เกาะ
• บรรทัดที่ $i$ ($1 \le i \le N$) ของ $N$ บรรทัดถัดมามีจำนวนเต็ม $A_i,C_i$ คั่นด้วยช่องว่าง หมายความว่าปัจจุบันเครื่องรับบนเกาะ $i$ รับคลื่นจากเกาะ $A_i$ ได้ และมีค่าใช้จ่ายในการเปลี่ยนทิศทางเท่ากับ $C_i$

ข้อมูลส่งออก

พิมพ์ค่าใช้จ่ายต่ำสุดที่ทำให้ส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้ลงในข้อมูลส่งออกมาตรฐานหนึ่งบรรทัด

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $2 \le N \le 100\,000$
• $1 \le A_i \le N$ ($1 \le i \le N$)
• $A_i \ne i$ ($1 \le i \le N$)
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

งานย่อย

งานย่อย 1 [10 คะแนน]

• $N \le 10$

งานย่อย 2 [30 คะแนน]

• $N \le 15$

งานย่อย 3 [30 คะแนน]

• $N \le 3\,000$

งานย่อย 4 [30 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

4
2 2
1 4
1 3
3 1

ข้อมูลส่งออก 1

4

หมายเหตุ

เปลี่ยนทิศทางเครื่องรับบนเกาะ $2$ ให้รับคลื่นจากเกาะ $4$ ได้ จากนั้นจะส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้ โดยมีค่าใช้จ่าย $4$

ไม่ว่าจะเปลี่ยนทิศทางเครื่องรับอย่างไร ค่าใช้จ่ายก็ไม่ต่ำกว่า $4$ ดังนั้นจึงพิมพ์ $4$

ข้อมูลนำเข้า 2

4
2 2
1 6
1 3
3 1

ข้อมูลส่งออก 2

5

หมายเหตุ

ก่อนอื่นเปลี่ยนทิศทางเครื่องรับบนเกาะ $1$ ให้รับคลื่นจากเกาะ $4$ ได้ จากนั้นเปลี่ยนทิศทางเครื่องรับบนเกาะ $3$ ให้รับคลื่นจากเกาะ $2$ ได้ จะทำให้ส่งโทรเลขจากเกาะใดก็ได้ไปยังเกาะใดก็ได้ โดยมีค่าใช้จ่าย $2+3=5$

ไม่ว่าจะเปลี่ยนทิศทางเครื่องรับอย่างไร ค่าใช้จ่ายก็ไม่ต่ำกว่า $5$ ดังนั้นจึงพิมพ์ $5$

ข้อมูลนำเข้า 3

4
2 2
1 3
4 2
3 3

ข้อมูลส่งออก 3

4

หมายเหตุ

เปลี่ยนทิศทางเครื่องรับบนเกาะ $1$ และเกาะ $3$ ก็เพียงพอ

ข้อมูลนำเข้า 4

3
2 1
3 1
1 1

ข้อมูลส่งออก 4

0

หมายเหตุ

ไม่จำเป็นต้องเปลี่ยนทิศทางเครื่องรับบนเกาะใดเลย