Təhlükəsiz yol
Kiçik Peter şəhərin xəritəsini barlarla işarələnmiş şəkildə əldə edib. Peter barlara getməyi çox sevir. Aydındır ki, barlara gecə getmək daha maraqlıdır. Lakin, Peter bir barda oturmaqdan bezə bilər, buna görə də tez-tez bir axşamda bir neçə bara baş çəkir.
Bu gün Peter iki məkanı ziyarət etməyə qərar verib. Bəzi barlar arasında yollar mövcuddur. Qaranlıq küçələrdə təhlükə ola bilər, buna görə də Peter barlar arasındakı hər bir yolu təhlükə dərəcəsi ilə qiymətləndirib: dərəcə nə qədər böyükdürsə, yol o qədər təhlükəlidir. Bir bardan digərinə birbaşa yol olmaya bilər, lakin hər bir bar cütü arasında, bəlkə də bir neçə başqa bar vasitəsilə keçən bir yol var. Bu halda, bütün yolun təhlükəsi yoldakı ən təhlükəli yolun təhlükəsinə bərabərdir.
Peter ziyarət etməyi planlaşdırdığı mümkün bar cütlərinin siyahısını tərtib edib. Hər bir cüt üçün onların arasında ən təhlükəsiz yolu bilmək lazımdır. Peterə bu işdə kömək etmək sizin vəzifənizdir.
Giriş verilənləri
Birinci sətir boşluqlarla ayrılmış üç tam ədəd ehtiva edir: n m q (1 ≤ n ≤ 100000, 1 ≤ m, q ≤ 200000) – müvafiq olaraq, barların sayı, barlar arasındakı yolların sayı və ziyarət üçün mümkün cütlərin sayı. Sonra m sətir yolları təsvir edir, hər biri boşluqlarla ayrılmış üç ədəd ehtiva edir: a b c (0 ≤ a, b < n, 1 ≤ c ≤ 10000) – müvafiq olaraq, yol ilə birləşdirilən barlar və onun təhlükəsi. Son q sətir Peterin ziyarət edə biləcəyi bar cütlərini təsvir edir – hər biri boşluqla ayrılmış iki ədəd ehtiva edir: a b (0 ≤ a, b < n).
Çıxış verilənləri
Peterin siyahısındakı hər bir cüt üçün ayrı sətirdə cavabı çıxarın – barlar arasındakı ən təhlükəsiz yolun təhlükəsi.