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

---

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

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

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

ورودی

در سطر اول ورودی دو عدد طبیعی $n$، تعداد شهر‌ها و $m$، تعداد جاده‌ها، آمده است.

در $m$ سطر بعد در هر سطر سه عدد طبیعی $u$ و $v$ و $l$ آمده است که نشان‌دهنده یک جاده دوطرفه قدیمی به طول $l$ بین دو شهر $u$ و $v$ است.

تضمین می‌شود بین هر دو شهر حداکثر یک جاده وجود دارد و هیچ شهری به خودش جاده ندارد.

در سطر بعد عدد طبیعی $q$، تعداد سناریو‌ها آمده است.

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

$$1\le n \le 100\ 000$$

$$1\le m,q \le 200\ 000$$

$$(u \ne v)$$$$1\le u, v \le n$$

$$1\le l \le 10^9$$

$$1\le v, k \le n$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۰	$ n,m,q \le 2\ 000 $
۲	۲۰	$ n,m \le 2\ 000 $
۳	۱۰	$ n \le 2\ 000 $
۴	۶۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
1 2 3
2 3 10
3 4 5
4 1 1
3
1 4
1 3 
4 2

خروجی نمونه ۱

5
3
1

ورودی نمونه ۲

3 1
1 2 3
3
1 2
1 3
3 1

خروجی نمونه ۲

3
-1
0

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون پنجم - ۱۳۹۳/۰۶/۱۵