عنوان پروژه‌ی جدید آقای مهندس «نوسازی جاده‌‌های نزدیک پایتخت» است. در کشور $n$ شهر وجود دارد که بعضی از آن‌ها با جاده‌های دوطرفه قدیمی به هم متصل شده‌اند. در این پروژه قرار است تعدادی از این جاده‌های قدیمی دوباره آسفالت شوند، به طوری که از حداقل $k$ شهر بتوان با استفاده از جاده‌های نوسازی شده به پایتخت رسید. (شامل خود پایتخت) از طرفی آقای مهندس می‌خواهد هر چه زودتر پروژه انجام شود تا به خانه‌اش برگردد.

روند اجرای پروژه به این‌ صورت است که آسفالت‌ کردن تمام جاده‌هایی که قرار است آسفالت شوند، به طور همزمان شروع می‌شود. می‌دانیم که آسفالت‌ کردن یک جاده به طول $l$، دقیقا $l$ روز طول می‌کشد. به عبارت دیگر پروژه آسفالت‌سازی به اندازه‌ی طول بلندترین جاده‌ای که قرار است آسفالت شود طول می‌کشد.

به ازای سناریو‌های مختلف که کدام شهر پایتخت باشد و مقدار $k$ چقدر باشد، کمترین زمان لازم برای انجام پروژه را پیدا کنید.

• در سطر اول ورودی دو عدد طبیعی $n$، تعداد شهر‌ها و $m$، تعداد جاده‌ها، آمده است.
• در $m$ سطر بعد در هر سطر سه عدد طبیعی $u$ و $v$ و $l$ آمده است که نشان‌دهنده یک جاده دوطرفه قدیمی به طول $l$ بین دو شهر $u$ و $v$ است.
• تضمین می‌شود بین هر دو شهر حداکثر یک جاده وجود دارد و هیچ شهری به خودش جاده ندارد.
• در سطر بعد عدد طبیعی $q$، تعداد سناریو‌ها آمده است.
• در هر یک از $q$ سطر بعد دو عدد $v$ و $k$ آمده است که نشان‌دهنده یک سناریو است که در آن لازم است از $k$ شهر بتوان به شهر $v$ (پایتخت) رسید.
• $1 \leq n \leq 1 * 10^5$
• $1 \leq m, q \leq 2 * 10^5$
• $(u \neq v) 1 \leq u, v \leq n$
• $1 \leq l \leq 10^9$
• $1 \leq v, k \leq n$

در $q$ سطر خروجی، در هر سطر پاسخ یک سناریو را چاپ کنید. در صورتی که $k$ شهر (شامل خود شهر $v$) وجود نداشته باشند که بتوان از آن‌ها به شهر $v$ رسید، عدد  $-1$ را چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $n, m, q \leq 2000$
• زیرمسئله دوم (۲۰ نمره): $n, m \leq 2000$
• زیرمسئله سوم (۱۰ نمره): $n \leq 2000$
• زیرمسئله چهارم (۶۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل