Cổng Dịch Chuyển

Cho một mạng lưới gồm $N$ đỉnh và $2N$ cổng dịch chuyển (portal). Mỗi cổng nối hai đỉnh khác nhau, và mỗi cổng xuất hiện trong danh sách kề của đúng hai đỉnh.

Mỗi đỉnh $v$ có đúng 4 cổng kề: $p_{v,1},p_{v,2},p_{v,3},p_{v,4}$. Các cổng được ghép cặp: $(p_{v,1},p_{v,2})$ và $(p_{v,3},p_{v,4})$. Người chơi có thể:

• Di chuyển qua một cổng từ đỉnh này sang đỉnh kia
• Chuyển đổi giữa hai cổng cùng cặp tại một đỉnh

Tại mỗi đỉnh $v$, bạn có thể hoán đổi cách ghép cặp (thay vì ghép $(p_{v,1},p_{v,2})$ và $(p_{v,3},p_{v,4})$, ghép $(p_{v,1},p_{v,3})$ và $(p_{v,2},p_{v,4})$) với chi phí $c_v$.

Hãy tìm chi phí nhỏ nhất để tất cả $4N$ vị trí (cổng tại đỉnh) đều liên thông với nhau.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Mỗi dòng gồm 5 số nguyên $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$

Dữ liệu ra

Một số nguyên duy nhất: chi phí nhỏ nhất.

Ràng buộc

• $2\le N\le {10}^5$
• $1\le c_v\le 1000$
• Các nhãn cổng từ $1$ đến $2N$
• Mỗi nhãn cổng xuất hiện đúng hai lần

Ví dụ