Tam Bak
Avropa boyunca avtomobil səyahətinizdən sonra qəbzlərə baxarkən, ziyarət etdiyiniz şəhərlərdə benzin qiymətlərinin fərqli olduğunu gördünüz. Ola bilsin ki, yanacaq doldurmağı daha ağıllı planlasaydınız, bir az qənaət edə bilərdiniz.
Başqa turistlərə kömək etmək (və növbəti dəfə özünüz qənaət etmək) üçün şəhərlər arasında ən ucuz səyahət yolunu tapmaq üçün bir proqram yazmaq istəyirsiniz, yolda yanacaq dolduraraq. Bütün avtomobillərin hər məsafə vahidi üçün bir yanacaq vahidi istifadə etdiyini və boş yanacaq çəni ilə başladığını qəbul edirik.
Giriş verilənləri
Birinci sətir n (1 ≤ n ≤ 1000) və m (0 ≤ m ≤ 10000) - şəhərlərin və yolların sayını verir. Sonra n tam ədəd p_i (1 ≤ p_i ≤ 100) gəlir, burada p_i i-ci şəhərdə yanacaq qiymətidir. Ardınca m sətir üç tam ədəd u, v (0 ≤ u, v < n) və d (1 ≤ d ≤ 100) ilə gəlir, bu, u və v arasında uzunluğu d olan bir yol olduğunu bildirir. Daha sonra q (1 ≤ q ≤ 100) sayını verən bir sətir gəlir, sorğuların sayını və q sətir üç tam ədəd c (1 ≤ c ≤ 100), s və e ilə gəlir, burada c nəqliyyat vasitəsinin yanacaq tutumu, s başlanğıc şəhər və e məqsəddir.
Çıxış verilənləri
Hər sorğu üçün, verilmiş tutumlu avtomobillə s şəhərindən e şəhərinə ən ucuz səyahətin qiymətini çıxarın, ya da verilmiş avtomobillə s şəhərindən e şəhərinə getməyin mümkün olmadığını bildirin.