Little Fabijan rất thích uống cafe và đi du lịch. Anh muốn thưởng thức cafe ở ~N~ thành phố trong đất nước của mình. Các thành phố được đánh số từ ~1~ đến ~N~ và có~ N -1~ con đường hai chiều nối giữa các thành phố sao cho với hai thành phố bất kỳ đều có đường đi giữa chúng. Fabijan quyết định đi du lịch để thưởng thức cafe ở mỗi thành phố theo trình tự từ thành phố ~1~ đến thành phố ~N~. Vì vậy, Fabijan bắt đầu từ thành phố ~1~, uống ly cafe đầu tiên ở đây, và đi đến thành phố ~2~ để uống ly cà phê thứ hai. Trong quá trình di chuyển, Fabijan có thể đi qua một số thành phố trung gian nhưng anh ta không uống cafe ở các thành phố trung gian. Sau khi uống cafe ở thành phố ~2~, Fabijan tiếp tục đến thành phố ~3~, và cứ tiếp tục chuyến du lịch thưởng thức cafe cho đến khi đến được thành phố ~N~, nơi mà anh ta uống ly cafe thứ ~N~.

Để đi qua một con đường, Fabijan cần phải mua vé. Con đường thứ ~i~ có ~2~ loại vé: Vé đi một lần có giá ~C_{i1}~, vé đi nhiều lần có giá ~C_{i2}~. Fabijan có thể mua vé đi một lần mỗi khi đi qua con đường nào đó hoặc chọn mua vé đi nhiều lần để không phải mua vé lại.

Yêu cầu

Tính số tiền ít nhất Fabijan dùng mua vé để hoàn thành chuyến du lịch của mình.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~N~ (~2 \leq N \leq 200 000~).

Dòng thứ ~i~ trong ~N-1~ dòng tiếp theo chứa ~4~ số nguyên ~A_i, B_i, C_{i1}, C_{i2}~ (~1 \leq A_i, B_i \leq N, 1 \leq C_{i1}, C_{i2} \leq 100 000~), thể hiện thành phố ~A_i~ và ~B_i~ có đường nối trực tiếp với giá vé ~C_{i1}~ và ~C_{i2}~.

Dữ liệu ra

Một số nguyên, số tiền ít nhất Fabijan dùng mua vé để hoàn thành chuyến du lịch của mình.

Subtasks

• Subtask ~1~ (~20% ~ điểm): ~2 \leq N \leq 2000~
• Subtask ~2~ (~25% ~ điểm): Mỗi thành phố sẽ có nhiều nhất là hai con đường nối trực tiếp với thành phố khác.
• Subtask ~3~ (~65% ~ điểm): Không có ràng buộc thêm.

Sample Input

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

Sample Output

10

Nguồn: COCI 2020