Điều ước

Trong thế giới cổ tích, Alice đang tham gia một thử thách do một phù thủy đặt ra. Phù thủy dẫn Alice tới một tầng hầm gồm N căn phòng và cho biết trong mỗi phòng đều có một viên pha lê. Alice cần phải thu thập toàn bộ pha lê ở cả N căn phòng để nhận được một điều ước từ phù thủy.

Bên cạnh tầng hầm có một tấm biển chỉ dẫn gồm bản đồ và một số quy tắc. Sau khi xem bản đồ, Alice nhận ra tầng hầm này có cấu trúc dạng cây và các phòng được kết nối với nhau thông qua các hành lang. Ngoài ra, việc di chuyển qua mỗi hành lang sẽ tiêu tốn một lượng năng lượng nhất định.

Alice có quyền chọn bất kỳ căn phòng nào làm vị trí xuất phát để bắt đầu thử thách. Một điểm đặc biệt mà Alice nhận thấy là cô có thể hoán đổi mức tiêu hao năng lượng giữa hai hành lang bất kỳ với số lần tùy ý, miễn là việc này được thực hiện trước khi cô chọn phòng xuất phát.

Hãy giúp Alice nhận được điều ước từ phù thủy với tổng lượng năng lượng tiêu hao là ít nhất.

Đầu vào:

• Dòng đầu tiên chứa số nguyên N ($2 \leq N \leq 10^5$).
• $N - 1$ dòng tiếp theo, mỗi dòng chứa 3 số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$) mô tả một hành lang nối giữa phòng u và phòng v với mức tiêu hao năng lượng là w.

Ràng buộc:

• Subtask 1 $(15 \%)$: Mỗi phòng được nối với tối đa 2 hành lang.
• Subtask 2 $(85 \%)$: Các trường hợp còn lại.

Đầu ra:

• In ra một số nguyên duy nhất là lượng năng lượng tiêu hao ít nhất để Alice có thể thu thập được pha lê trong tất cả các phòng.

Giải thích:

.image-container { display: flex; justify-content: space-between; } .image-container img { width: 50%; max-width: 95%; border-radius: 5px; }

Với bản đồ ban đầu, Alice chỉ cần hoán đổi mức năng lượng giữa hành lang nối hai phòng (3, 4) và hành lang nối hai phòng (1, 2).

Sau đó, Alice sẽ thu thập các viên pha lê theo lộ trình: 5 -> 3 -> 4 -> 3 -> 1 -> 2

Ví dụ 1:

Đầu vào:

5
1 2 2
1 3 2
3 4 3
3 5 4

Đầu ra:

13