Təhlükəsiz yol#3206
Peter şəhərin xəritəsini əldə edib və xəritədə pablar işarələnib. Peter pabları ziyarət etməyi sevir və təbii ki, daha çox həyəcan üçün axşam getməyi üstün tutur. Sadəcə bir pabda oturmaqdan tez sıxılır, ona görə də bir axşamda tez-tez bir neçə pabı gəzir.
Bu gün Peter iki pabı ziyarət etməyə qərar verib. Bəzi pablar arasında yollar var. Gecə bu yollar təhlükəli ola bilər, ona görə də Peter hər yola bir risk səviyyəsi təyin edib: dəyər nə qədər böyükdürsə, risk də o qədər yüksəkdir. İki müəyyən pab arasında birbaşa yol olmaya bilər, lakin digər pablar vasitəsilə həmişə bir yol mövcuddur. Bu halda, bütün yolun riski marşrut boyunca yollar arasında ən yüksək riskin dəyərinə bərabər olur.
Peter ziyarət edə biləcəyi pab cütlüklərinin siyahısını tərtib edib. Hər bir cütlük üçün o, aralarındakı ən təhlükəsiz yolun riskini bilmək istəyir. Sənin vəzifən Peterə bu cütlüklərin hər biri üçün ən təhlükəsiz yolun riskini müəyyən etməyə kömək etməkdir.
Birinci sətirdə üç boşluqla ayrılmış tam ədəd verilir: (1 \leq n \leq 100000, 1 \leq m,\ q \leq 200000) — pabların sayı, aralarındakı yolların sayı və nəzərdən keçiriləcək cütlüklərin sayı.
Növbəti sətirin hər biri bir yolu təsvir edir. Hər sətirdə üç boşluqla ayrılmış tam ədəd verilir: (0 \leq a,\ b < n, 1 \leq c \leq 10000) — iki pab və aralarındakı yolun riski.
Sonrakı sətirin hər biri Peterin ziyarət edə biləcəyi pab cütlərini təsvir edir. Hər sətirdə iki boşluqla ayrılmış tam ədəd verilir: (0 \leq a,\ b < n).
Peterin siyahısındakı hər bir cütlük üçün pablar arasındakı ən təhlükəsiz yolun riskini bir sətirdə olmaqla çap et.
Nümunə 1