Cậu bé Fabijan rất thích quán bar và du lịch. Cậu ấy muốn uống cà phê bia ở mỗi thị trấn trong số ~N~ thị trấn của đất nước mình, được đánh số tiện lợi từ ~1~ đến ~N~. Các thị trấn được kết nối với nhau qua ~(N - 1)~ con đường hai chiều sao cho mỗi thị trấn có thể đến được thị trấn khác bằng cách đi qua một số con đường. Fabijan quyết định uống cà phê ở mỗi thị trấn theo thứ tự từ thị trấn số ~1~ đến thị trấn số ~N~. Do đó, cậu bắt đầu từ thị trấn số ~1~ (nơi cậu uống cà phê đầu tiên) và di chuyển đến thị trấn số ~2~ để uống cà phê tiếp theo. Trong chuyến đi đó, cậu có thể đi qua nhiều thị trấn khác nhưng sẽ không dừng lại uống cà phê tại các thị trấn đó. Sau khi uống cà phê ở thị trấn ~2~, cậu sẽ tiếp tục hành trình đến thị trấn ~3~, và cứ thế cho đến khi cuối cùng đến thị trấn ~N~ nơi cậu sẽ uống cà phê cuối cùng.

Để đi qua một con đường nhất định, cậu cần có vé hợp lệ. Con đường thứ ~i~ có thể đi qua nếu bạn có vé một lần với giá ~C_{i1}~ euro hoặc vé nhiều lần với giá ~C_{i2}~ euro. Đối với mỗi con đường, Fabijan có thể quyết định mua vé một lần mỗi khi cần đi qua con đường đó hoặc cậu có thể chọn mua vé nhiều lần một lần.

Viết chương trình tính số euro nhỏ nhất Fabijan cần chi tiêu cho vé để hoàn thành thành công chuyến đi của mình.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \leq N \leq 200 000)~ từ mô tả bài toán.
• Trong dòng thứ ~i~ của ~(N - 1)~ dòng tiếp theo có bốn số nguyên ~A_i, B_i, C_{i1}, C_{i2}~ ~(1 \leq A_i, B_i \leq N, 1 \leq C_{i1} \leq C_{i2} \leq 100 000)~ biểu thị thị trấn ~A_i~ và ~B_i~ được kết nối bằng một con đường với giá vé ~C_{i1}~ và ~C_{i2}~.

Output

• Trong một dòng xuất chi phí đi lại nhỏ nhất.

Chú ý

• Subtask 1: 20 điểm với ~2 \leq N \leq 2000~.
• Subtask 2: 25 điểm, mỗi thị trấn sẽ được kết nối trực tiếp với tối đa hai thị trấn khác.
• Subtask 3: 65 điểm không có ràng buộc thêm.

Sample Input 1

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

Sample Ouput 1

10

Sample Input 2

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

Sample Ouput 2

16

Sample Input 3

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

Sample Ouput 3

11

Giải thích

Giải thích ví dụ đầu tiên: Fabijan đầu tiên di chuyển từ thị trấn ~1~ đến thị trấn ~2~ và tối ưu nhất là mua vé nhiều lần (~5~ euro) cho con đường kết nối giữa hai thị trấn này. Sau đó, cậu ấy di chuyển từ thị trấn ~2~ đến thị trấn ~3~ qua thị trấn ~1~. Cậu ấy đã có vé nhiều lần đi từ ~2~ đến ~1~ và mua một vé một lần từ thị trấn ~1~ đến thị trấn ~3~ (~2~ euro). Trong chuyến đi từ thị trấn ~3~ đến thị trấn ~4~, cậu ấy mua thêm một vé một lần từ thị trấn ~3~ trở lại thị trấn ~2~ (~2~ euro) và sau đó mua một vé một lần từ thị trấn ~2~ đến thị trấn ~4~ (~1~ euro). Tổng cộng, cậu ấy đã chi tiêu ~5 + 2 + 2 + 1 = 10~ euro.