Hədiyyə#2007
Olimpiya krallığı şəhər və ikitərəfli yoldan ibarətdir. Hər yol məhz iki şəhəri birləşdirir, iki şəhərin arasında bir neçə yol ola bilər. Eyni zamanda, bəzi yollar öz üzərinə qapalı dairə (loop) şəklində olub, şəhəri özü ilə birləşdirə bilər.
Bütün yollar daim quldurlar tərəfindən qarət olunur. Son zamanlar quldurlar qarət etməkdən yorulublar və Olimpiya krallığının kralına qızıl və gümüş sikkələrdən ibarət hədiyyə təklif ediblər. Hər yol üçün məlumdur ki, bu yolun qarətinin dayanması üçün hədiyyədə ən az g_i qızıl və ən az s_i gümüş sikkə olmalıdır. Yəni, əgər hədiyyədə qızıl və gümüş sikkə varsa, onda g_i \leq a və s_i \leq b olan bütün yolların qarəti dayandırılır.
Kralın xəzinəsində nə qızıl, nə də gümüş sikkə var, yalnız Olimpiya tüqrükləri var. Bir qızıl sikkənin qiyməti , bir gümüş sikkənin qiyməti isə tüqrükdür. Kral istəyir ki, elə bir hədiyyə göndərsin ki, hər bir şəhər cütü arasında ən az bir təhlükəsiz yol olsun.
Verilən məlumatlara görə, şəhərlər, yollar və sikkələrin qiymətlərinə əsasən belə bir hədiyyə üçün lazım olan minimal tüqrük miqdarını tapın.
Birinci sətirdə və (2 \leq N \leq 200, 1 \leq M \leq 50\,000) tam ədədləri — şəhərlərin və yolların sayı verilir.
İkinci sətirdə iki tam ədəd və (1 \leq G, S \leq 10^9) — qızıl və gümüş sikkələrin tüqrüklə qiymətləri verilir.
Növbəti sətirin hər birində dörd tam ədəd x_i, y_i, g_i, s_i verilir. x_i və y_i -ci yolun birləşdirdiyi şəhərlərin nömrələridir (1 \leq x_i, y_i \leq N), g_i və s_i (1 \leq g_i, s_i \leq 10^9) — -ci yolun qarətinin dayanması üçün hədiyyədə tələb olunan minimum qızıl və gümüş sikkə sayıdır.
Şəhərlər -dən -ə kimi nömrələnmişdir. Bir şəhər cütü arasında bir neçə yol ola bilər. Bəzi yollar şəhəri özü ilə birləşdirə bilər.
Bir tam ədəd çıxarın — kralın qızıl və gümüş sikkə almaq üçün xərcləməli olduğu minimal tüqrük sayı, əgər bu mümkün deyilsə, yazın.
Nümunə 1