Ucuz səyahət
İvan Skoroxod növbəti proqramlaşdırma müsabiqəsinə gedəcək və yol xərclərini öz şəxsi vəsaitlərindən ödəməlidir. Onun cəmi s avrosu var. Buna görə də, o, ictimai nəqliyyat qrafiklərini və qiymətləri diqqətlə araşdırdı. Skoroxodun yerləşdiyi yeri 1, müsabiqənin keçirildiyi yeri n və 2, 3, ..., n - 1 - onun hərəkət edə biləcəyi digər kəndlər kimi təyin edək. İnternetdə İvan m səyahət imkanlarını tapdı: kənd v-dən kənd w-yə (həmçinin w-dən v-yə) avtobus t saat gedir, hər iki istiqamət üçün xərclər e avro təşkil edir. v və w arasında bir neçə avtobus ola bilər və v-dən w-yə gedən müxtəlif avtobuslar fərqli vaxtlarda və fərqli bilet qiymətləri ilə gedə bilər.
Kənd 1-dən kənd n-ə qədər s avrodan az və ya bərabər qiymətə səyahəti tapacaq proqram yazın. Əgər bir neçə belə səyahət varsa, Skoroxodun avtobuslarda minimum vaxt keçirəcəyi səyahəti tapın.
Giriş məlumatları
Birinci sətir təbii ədədlər s, n və m (s ≤ 2000, n ≤ 3000, m ≤ 5000) ehtiva edir. Növbəti m sətirin hər biri 4 tam ədəd ehtiva edir - bir səyahət imkanının v, w, t və e parametrləri (1 ≤ v ≤ n, 1 ≤ w ≤ n, 1 ≤ t ≤ 100, 1 ≤ e ≤ 100).
Çıxış məlumatları
Tapılan səyahətin müddətini çıxış edin. Əgər s avrodan az və ya bərabər qiymətə səyahət mövcud deyilsə, -1 çıxış edin.