Во земјата Дрвенија има N градови, нумерирани секој со различен од броевите од 1 до N. Градовите се поврзани со N-1 патишта, секој од кои поврзува директно два града во двете насоки. Мрежата од патишта е така организирана да може да се стигне од секој до секој друг град преку еден или повеќе од патиштата.

Петар сака да поднесе петиција до владата, теретаните да станат бесплатни за користење. За таа цел, тој мора да собере потписи од сите градоначалници, ама на петицијата градоначалниците мора да се потпишат по ред (прво тој од првиот град, па тој од вториот, па од третиот…).

Денес е 16-ти април, и Петар има рок до 30-ти април да ја заврши задачата. Тој е сега во првиот град каде ќе земе потпис од градоначалникот и потоа со автобус ќе отпатува до соседниот град, со намера да стигне до градот 2, па откако ќе заврши работа во градот 2 ќе тргне накај градот 3, и се така дури не стигне до N каде ќе го заврши патувањето. Иако во меѓувреме Петар ќе влегува и во други градови, тој нема да може тогаш да го земе потписот, оти нема да биде дојден редот за потпишување на соодветниот градоначалник.

Автобуси возат само меѓу соседни градови. За да се возиме во автобус, или купуваме обичен билет при секое возење или купуваме месечен билет па може да се возиме колку пати сакаме. За секој пат, меѓу два града, ја знаеме цената C₁ за еднократно патување и цената C₂ за месечен билет. Петар за секој пат може да избере дали ќе купи месечен билет (за месец април), или ќе плаќа при секое патување.

Ваша задача е да пресметате колку најмалку пари Петар мора да потроши за билети за да може успешно да го изврши патувањето.

Влез

Во првиот ред е даден бројот N (2 ≤ N ≤ 200 000).
Во i-тиот од следните N - 1 редови, има по 4 цели броеви: A_i, B_i, C_i1, C_i2 (1 ≤ A_i, B_i ≤ N, 1 ≤ C_i1 ≤ C_i2 ≤ 100 000), што означува дека градовите A_i и B_i се поврзани со пат и автобуските билети се со цена C_i1 и C_i2, според описот од задачата.

Забелешка.
Во подзадача 1, за 18 поени: 2 ≤ N ≤ 2000.
Во подзадача 2, за 21 поен: секој град ќе биде поврзан со најмногу 2 други града.
Во подзадача 3, за 61 поен: нема дополнителни ограничувања.

Излез

Во единствениот ред отпечатете ја најмалата можна цена на патувањето.

Ограничувања

Временско ограничување: 300 milliseconds
Мемориско ограничување: 512 megabytes

Примери

влез
4
1 2 5 9
1 3 6 13
1 4 3 4

излез
24

влез
5
1 4 4 5
2 4 5 9
3 5 3 10
4 5 6 11

излез
30

Објаснување за првиот пример:
Петар прво патува од град 1 до град 2 и за него е оптимално да купи месечен билет (9 пари) за патот кој ги поврзува. Потоа тој патува од град 2 до град 3 преку град 1. Веќе има месечен билет кој го води од 2 до 1 и купува обичен билет од град 1 до град 3 (6 пари). На патувањето до град 4, минува преку град 1 и пак купува обичен билет од град 3 до град 1 (6 пари), и потоа купува обичен билет кој носи од град 1 до град 4 (3 пари). Вкупно потрошил 9 + 6 + 6 + 3 = 24.