Một nhà Vua đã giành được quyền kiểm soát ở một vùng đất xa xôi. Để thu được lợi nhuận từ vùng đất mới của mình, nhà vua cho xây dựng các con đường để thu lệ phí của khách du lịch đi qua. Người vẽ bản đồ hoàng gia đã cung cấp bản đồ của vùng đất mới với các thị trấn và các con đường có thể xây dựng: hai thị trấn bất kỳ được kết nối bằng đúng một đường đi (gồm dãy các con đường từ một thị trấn đến một thị trấn khác). Với mỗi con đường, thủ quỹ hoàng gia cho biết lợi nhuận từ việc thu lệ phí của con đường đó. Lợi nhuận này có thể âm, nghĩa là chi phí xây dựng cao hơn so với thu lệ phí con đường đó.

Yêu cầu: Hãy giúp nhà vua lựa chọn các con đường cần xây dựng sao cho tổng lợi nhuận thu được tối đa và các con đường được lựa chọn xây dựng phải được kết nối với nhau, tức là luôn đi được từ một con đường được xây dựng đến một con đường được xây dựng bất kỳ khác bằng cách sử dụng các con đường được xây dựng.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~) là số con đường có thể xây dựng.
• Mỗi dòng trong ~n~ dòng tiếp theo chứa 3 số nguyên ~a, b, p~ (~1 \le a, b \le 2 \times 10^5~, ~-1000 \le p \le 1000~), mô tả một con đường có thể xây dựng nối hai thị trấn ~a, b~ và lợi nhuận ~p~ nếu con đường này được xây dựng. Các thị trấn được đánh số có thể không liên tiếp và các con đường là hai chiều.

Output

• Ghi ra một số nguyên là tổng lợi nhuận tối đa bằng cách chọn các con đường xây dựng như mô tả ở trên.

Sample Input 1

4
1 2 -7
3 2 10
2 4 2
5 4 -2

Sample Output 1

12