Round Trip
Jim, dağlıq bir bölgədə yerləşən bir şəhərdəki ən yaxın dostlarından birini ziyarət etməyi planlaşdırır. Əvvəlcə o, öz doğma şəhərindən çıxaraq təyinat şəhərinə gedir. Bu, getmə mərhələsi adlanır. Sonra o, öz doğma şəhərinə geri dönür. Bu, qayıtma mərhələsi adlanır. Sizdən bu səfərin minimum ümumi xərcini, yəni getmə və qayıtma mərhələlərinin xərclərinin cəmini tapmaq üçün bir proqram yazmağınız tələb olunur.
Bu iki şəhəri əhatə edən şəhərlər şəbəkəsi mövcuddur. Bu şəbəkədəki hər bir yol tək istiqamətlidir, yəni yalnız müəyyən istiqamətə doğru istifadə edilə bilər. Hər bir yol müəyyən bir xərci tələb edir.
Yolların xərcinə əlavə olaraq, yolda hər bir şəhərdən keçmək üçün müəyyən edilmiş bir rüsum ödəmək lazımdır. Lakin, bu şəhərin viza rüsumu olduğu üçün eyni şəhərə ikinci və ya daha sonrakı ziyarətlərdə rüsum ödəmək lazım deyil.
Hər bir şəhərin hündürlüyü (hündürlüyü) verilir. Getmə mərhələsində enən yolların istifadəsi qadağandır. Yəni, şəhər a-dan şəhər b-yə gedərkən, a-nın hündürlüyü b-nin hündürlüyündən böyük olmamalıdır. Qayıtma mərhələsində isə oxşar şəkildə qalxan yolların istifadəsi qadağandır. Əgər a və b şəhərlərinin hündürlükləri bərabərdirsə, a-dan b-yə olan yol hər iki mərhələdə istifadə edilə bilər.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir, hər biri aşağıdakı formatda.
Bir datasetdəki hər bir giriş elementi qeyri-mənfi tam ədəddir. Bir sətirdəki giriş elementləri boşluqla ayrılır.
n şəbəkədəki şəhərlərin sayıdır. m (tək istiqamətli) yolların sayıdır. Siz 2 ≤ n ≤ 50 və 0 ≤ m ≤ n(n-1) bərabərsizliklərinin doğru olduğunu qəbul edə bilərsiniz. Şəhərlər 1-dən n-ə qədər nömrələnib. Şəhər 1 Jim'in doğma şəhəridir və şəhər n təyinat şəhəridir.
d_i şəhər i-nin viza rüsumudur və e_i onun hündürlüyüdür. Siz 2 ≤ i ≤ n-1 üçün 1 ≤ d_i ≤ 1000 və 1 ≤ e_i ≤ 999 olduğunu qəbul edə bilərsiniz. Şəhərlər 1 və n viza rüsumu tətbiq etmir. Şəhər 1-in hündürlüyü 0, şəhər n-in hündürlüyü isə 1000-dir. Bir neçə şəhər eyni hündürlüyə malik ola bilər, lakin eyni hündürlüyə malik olan şəhərlərin sayının 10-dan çox olmadığını qəbul edə bilərsiniz.
j-ci yol şəhər a_j-dən şəhər b_j-yə c_j xərci ilə gedir (1 ≤ j ≤ m). Siz 1 ≤ a_j ≤ n, 1 ≤ b_j ≤ n və 1 ≤ c_j ≤ 1000 olduğunu qəbul edə bilərsiniz. Siz birbaşa a_j-dən b_j-yə gedə bilərsiniz, lakin b_j-dən a_j-yə gedə bilməzsiniz, əgər b_j-dən a_j-yə ayrıca bir yol verilməyibsə. Eyni istiqamətə doğru eyni şəhər cütünü birləşdirən iki yol yoxdur, yəni hər hansı i və j üçün i ≠ j, a_i ≠ a_j və ya b_i ≠ b_j. Özünü birləşdirən yollar yoxdur, yəni hər hansı j üçün a_j ≠ b_j.
Son datasetdən sonra iki sıfırdan ibarət bir sətir (boşluqla ayrılmış) gəlir.
Çıxış verilənləri
Girişdəki hər bir dataset üçün, səfərin viza rüsumları daxil olmaqla minimum ümumi xərcini əks etdirən bir sətir çıxarılmalıdır. Əgər belə bir səfər mümkün deyilsə, "-1" çıxarılmalıdır.