Đường vành đai

Có $N$ thành phố được nối với nhau bởi $N$ con đường tạo thành một vòng tròn: nếu bỏ chiều đi của các con đường thì mỗi thành phố nối trực tiếp với đúng hai thành phố khác và từ bất kỳ thành phố nào cũng đi được đến mọi thành phố còn lại.

Hiện tại, mỗi con đường đã được ấn định một chiều đi một chiều. Tuy nhiên có thể có những cặp thành phố không thể đến được nhau bằng chiều hiện tại. Chính phủ muốn đảo chiều một số con đường (đảo chiều con đường thứ $i$ tốn $c_i$ đồng) sao cho từ mọi thành phố đều có thể đi đến mọi thành phố khác.

Hãy tính chi phí nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ — số thành phố (và cũng là số con đường).
• $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i,b_i,c_i$ mô tả một con đường đi từ thành phố $a_i$ đến thành phố $b_i$ với chi phí đảo chiều là $c_i$.

Dữ liệu ra

In ra một số nguyên duy nhất — chi phí nhỏ nhất cần bỏ ra để mọi thành phố đều đi được đến nhau.

Ràng buộc

• $3\le N\le 100$
• $1\le a_i,b_i\le N$, $a_i\ne b_i$
• $1\le c_i\le 100$
• Đồ thị (bỏ chiều) tạo thành đúng một vòng tròn đi qua mọi thành phố.

Ví dụ