Hədiyyə
Olimpiya krallığında N şəhər və M ikitərəfli yol var, hər biri dəqiq iki şəhəri birləşdirir. İki şəhər arasında bir neçə yol ola bilər. Bütün yollar daim quldurlar tərəfindən qarət olunur. Son zamanlar quldurlar qarət etməyə güc sərf etməkdən beziblər və Olimpiya krallığının qüdrətli və ədalətli kralına kommersiya təklifi ilə müraciət ediblər. Bu təklifə əsasən, kral quldurlara qızıl və gümüş sikkələrdən ibarət bir hədiyyə göndərməlidir. Kralın lütfkarlığına cavab olaraq, quldurlar müəyyən yolları qarət etməyi dayandıracaqlar. Hər bir yol üçün hədiyyədə tələb olunan minimum qızıl və minimum gümüş sikkə sayı müəyyən edilib ki, onun qarət olunması dayansın. Yəni, əgər hədiyyədə K qızıl və L gümüş sikkə varsa, o zaman qarət olunması dayandırılan yolların qızıl sikkə sayı K-dən az və ya bərabər, gümüş sikkə sayı isə L-dən az və ya bərabər olmalıdır.
Kralın xəzinəsində heç bir qızıl və ya gümüş sikkə yoxdur, lakin Olimpiya Tüqrükləri var. Bir qızıl sikkənin tüqrüklə qiyməti G, gümüş sikkənin qiyməti isə S-dir. Kral çox istəyir ki, quldurlara hədiyyə göndərdikdən sonra hər bir şəhər cütü arasında, bəlkə də digər şəhərlərdən keçən, ən azı bir təhlükəsiz yol olsun.
Şəhərlər və yollar haqqında verilən məlumatlara və sikkələrin qiymətlərinə əsasən, krallığın hər bir şəhər cütü arasında təhlükəsiz yollar əldə etmək üçün kralın xərcləməli olduğu minimum tüqrük sayını tapacaq bir proqram yazın.
Giriş verilənləri
Birinci sətir Olimpiya krallığında şəhərlərin və yolların sayını göstərən iki tam ədəd N və M (2 ≤ N ≤ 200, 1 ≤ M ≤ 50 000) ehtiva edir. İkinci sətir sikkələrin qiymətlərini göstərən G və S (1 ≤ G, S ≤ 10^9) ədədlərini ehtiva edir. Növbəti M sətir yollar və quldurların təklifi haqqında məlumatı ehtiva edir. i+2-ci giriş sətirində 4 təbii ədəd var, ilk ikisi i-ci yol ilə birləşdirilən şəhərlərin nömrələridir (şəhərlər 1-dən N-ə qədər nömrələnir), növbəti ikisi isə quldurlara hədiyyə göndərmək üçün tələb olunan minimum qızıl və minimum gümüş sikkə sayıdır ki, i-ci yolun qarət olunması dayansın. Hər iki ədəd 10^9-u keçmir.
Çıxış verilənləri
Bir tam ədəd çıxarın - kralın qızıl və gümüş sikkələr almaq üçün xərcləməli olduğu minimum tüqrük sayı, ya da əgər heç bir tüqrük miqdarı kömək etmirsə, -1.