Şəhər Sürüşü
San Fransiskoya boş vaxtlarınızda tez-tez getməyə başladınız və şəhərdə maşın sürməyin böyük bir əziyyət olduğunu anladınız. Ancaq şəhərdə sizi maraqlandıran yalnız N məkan var və siz sürücülük təcrübənizi yaxşılaşdırmağa qərar verdiniz. GPS-ə malik olmadığınız və çox fərqli marşrutları yadda saxlaya bilmədiyiniz üçün istiqamətləri və N fərqli məkan cütləri arasında getmək üçün nə qədər vaxt lazım olduğunu yazdınız (hər iki istiqamətdə eyni), yalnız bu yolları istifadə edərək istənilən məkandan digərinə gedə biləcəyinizə əmin oldunuz.
İndi həftə sonu üçün səyahətinizi planlaşdırırsınız və yalnız yazdığınız marşrutlardan istifadə edərək şəhərdəki Q məkan cütü arasında ən sürətli yolu tapmalısınız.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Birinci sətir maraqlandığınız məkanların sayı və yazdığınız marşrutların sayı olan tək tam ədəd N, 3 ≤ N ≤ 100000 ehtiva edir. Növbəti N sətirin hər biri üç tam ədəd u, v və w (1 ≤ w ≤ 1000) ehtiva edir, bu da məkan u-dan məkan v-yə və əksinə (0-indekslənmiş) istiqamətləriniz olduğunu və bunun w vaxt aldığını göstərir. Növbəti sətir Q, 1 ≤ Q ≤ 10000, səyahət vaxtını hesablamaq lazım olan məkan cütlərinin sayını ehtiva edən tək tam ədəd ehtiva edir. Növbəti Q sətirin hər biri iki tam ədəd u və v ehtiva edir, bu da məkan u-dan məkan v-yə getmək üçün minimum vaxtı tapmalı olduğunuzu göstərir. Giriş N = 0 olan bir sətirlə bitir.
Çıxış verilənləri
Hər test halı üçün, tapdığınız ən sürətli marşrutlar üçün u və v məkan cütlərinin hər biri üçün Q sətir çap edin. Hər sətir sadəcə məkan u-dan məkan v-yə səyahət etmək üçün lazım olan minimum vaxtı ehtiva etməlidir.