Cậu bé Mika là một người rất thích đi du lịch cũng giao lưu với những người bạn từ nhiều nơi. Trên mạng xã hội, Mika đã làm quen được \(n\) người bạn và họ sinh sống tại \(n\) thành phố khác nhau trên đất nước. Các thành phố được đánh số từ \(1\) đến \(n\) và được nối với nhau thông qua \(n - 1\) con đường hai chiều sao cho có thể đến được mỗi thành phố từ bất kỳ thành phố nào khác bằng cách đi qua một số con đường, con đường thứ \(i\) kết nối trực tiếp hai thành phố \(a_i\) và \(b_i\).

Vào ngày cuối tuần, Mika quyết định đi đến thăm tất cả những người bạn mới này. Hiện tại, Mika đang ở thành phố thứ nhất và thăm được người bạn đầu tiên. Sau đó anh ấy quyết định thứ thăm người bạn sống ở thành phố thứ \(2\), rồi mới thăm đến người bạn sống ở thành phố thứ \(3\), ... cuối cùng là người bạn sống ở thành phố thứ \(n\). Để đi qua một con đường nhất định, Mika cần phải có một vé hợp lệ. Con đường thứ \(i\) có thể được đi qua nếu bạn có vé một lượt giá \(c_{i_1}\) đồng hoặc vé nhiều lượt giá \(c_{i_2}\) đồng. Vé một lượt chỉ cho phép đi qua con đường một lần, còn vé nhiều lượt thì không giới hạn số lần đi qua con đường đó. Mika muốn tiết kiệm chi phí di chuyển nên hãy giúp cậu ấy tính toán chi phí tối thiểu để Mika có thể đi thăm tất cả người bạn của mình.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((2 \leq n \leq 2 \times 10^5)\) là số lượng thành phố.
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(a_i, b_i, c_{i_1}, c_{i_2}\) \((1 \leq a_i,b_i \leq n, 1 \leq c_{i_1}, c_{i_2} \leq 10^5)\) mô tả một con đường.

Output

• Một số nguyên duy nhất là chi phí tối thiểu để Mika có thể đi thăm tất cả người bạn của mình.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(c_{i_1} = c_{i_2}\) với mọi \(1 \leq i \leq n - 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 2 \times 10^3\).
• Subtask \(3\) (\(20\%\) số điểm): Mỗi thành phố kết nối trực tiếp với tối đa hai thành phố khác.
• Subtask \(4\) (\(20\%\) số điểm): Các thành phố và các con đường tạo thành một cây nhị phân hoàn hảo với đỉnh \(1\) là gốc.
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

10

4
1 4 5 5
3 4 4 7
2 4 2 6

16

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

11