Topskiy informasiyanın çatdırılması üçün şəbəkə qurmaq istəyir. Şəbəkə şəkildə göstərildiyi kimi cari server və bir neçə güzgü serverindən təşkil olunur. Giriş verilənləri başlanğıc serverdə yerləşir (şəkil \textbf{1}-də kökdə), eyni zamanda onların nüsxələri bəzi güzgü serverlərə çatdırılır (şəkil \textbf{1}-də \textbf{2} və \textbf{5} təpələri). Qovşaq verilənlərin axtarılması üçün sorğu göndərən zaman, o verilənləri növbəti yerlərdə tapmağa çalışır. \begin{enumerate} \item Qovşaqda verilənlərin nüsxəsinin olmasını yoxlayırıq. Əgər belədirsə, sorğu yerinə yetirilmişdir. Əks halda \textbf{2}-ci addıma keçirik. \item Sorğunu \textbf{1}-ci addımın həyata keçirdiyi valideynə veririk. \end{enumerate} \includegraphics{https://static.e-olymp.com/content/74/74dc1d0e865c9bc90e76b6fa575090a3ee7fcb83.jpg} \textbf{C}(\textbf{v}) sorğusunun icrasının qiyməti yoldakı tillərin çəkilərinin cəmi kimi təyin edilir. Əgər \textbf{C}(\textbf{v}) \textbf{Q}(\textbf{v})-nin üst sərhəddindən böyük deyilsə, onda axtarışın qiyməti qəbul olunmuş sayılır. Topskiy \textbf{v} təpəsində verilənlər yazısında mənfi olmayan \textbf{S(v)} qiymətinin olmasını ehtimal edir. Cari server xüsusidir, onda verilənlərin saxlanılması qiyməti \textbf{0}-dır. Topskiy verilənlərin nüsxəsini serverdə elə yerləşdirmək istəyir ki, bütün təpələrin axtarış qiyməti münasib olsun, verilənlər yazısının ümumi qiyməti ən az olsun. \InputFile İlk sətir testlərin \textbf{t} (\textbf{t} ≤ \textbf{20}) sayını ehtiva edir. Hər bir test serverlərin sayını ifadə edən \textbf{n }(\textbf{1 }≤ \textbf{n} ≤ \textbf{1000}) tam ədədi ilə başlayır. Sonra hər biri \textbf{4} tam \textbf{F_v} (\textbf{0} ≤ \textbf{F_v} ≤ \textbf{n}), \textbf{Q_v}, \textbf{S_v} və \textbf{W_v} (\textbf{0} ≤ \textbf{Q_v}, \textbf{S_v}, \textbf{W_v} ≤ \textbf{10^5}) ədədlərini ehtiva edən \textbf{n} sətir verilir. \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}) sətrindəki \textbf{F_v} \textbf{i} təpəsinin atasını ifadə edir (əgər \textbf{F_v} \textbf{0}-a bərabərdirsə, inda \textbf{i} cari server sayılır, \textbf{Q_v} \textbf{-1}-ə bərabərdirsə, \textbf{S_v} və \textbf{W_v} \textbf{0}-a bərabərdir), \textbf{Q_v} axtarış qiymətinin üst sərhəddidir. \textbf{S_v} \textbf{i }təpəsindəki verilənlər yazısının qiymətinə bərabərdir, \textbf{W_v} isə \textbf{i} və \textbf{F_v} təpələrini birləşdirən tilin çəkisinə bərabərdir. \OutputFile Hər bir test üçün ayrı sətirdə verilənlərin saxlanılması üçün məsrəfin minimal qiymətini verməli.