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

---

خانم دکتر در پارک گم‌ شده‌ و آقای مهندس در حال گشتن پارک برای پیدا کردن اوست. می‌دانیم که در پارک $n$ تقاطع وجود دارد که با $n - 1$ گذرگاه به هم وصل شده‌اند، به طوری که می‌توان از هر تقاطعی به هر تقاطع دیگر رسید. (گراف جاده‌های پارک به شکل یک درخت است) خانم دکتر در تقاطع $e$ نشسته‌است و آقای مهندس که در تقاطع $s$ قرار دارد، می‌خواهد او را پیدا کند.

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

برنامه‌ای بنویسید که با گرفتن سناریو‌های مختلف مکان $s$ و $e$، امید ریاضی زمانی را که طول می‌کشد تا آقای مهندس خانم دکتر را پیدا کند، بیاید.

ورودی

سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد تقاطع‌ها و $q$، تعداد سناریو‌ها است.

در هر کدام از $n - 1$ سطر بعد، سه عدد طبیعی $u$ و $v$ و $t$ آمده است که به معنای وجود یک گذرگاه بین دو تقاطع $u$ و $v$ است که $t$ دقیقه زمان برای عبور از آن لازم است.

سپس در هر کدام از $q$ سطر بعدی دو عدد $s$، محل شروع حرکت آقای مهندس و $e$، تقاطعی که خانم دکتر در آن نشسته‌، آمده است.

$$1\leq n, q \leq 100\ 000$$

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

$$1\leq t \leq 1\ 000$$

$$1\leq s, e \leq n$$

خروجی

در $q$ سطر خروجی در هر سطر آن به ازای یک سناریو، امید ریاضی زمانی که طول می‌کشد تا آقای مهندس خانم دکتر را پیدا کند را چاپ کنید. اگر خطای نسبی پاسخ شما و پاسخ اصلی شما کمتر از $10^{-7}$ باشد، جواب شما پذیرفته خواهد شد.

زیرمساله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۰	$ n \le 10 $
۲	۲۰	$ n \le 1\ 000 $
۳	۷۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 3
1 2 10
2 3 20
1 2
2 3 
1 3

خروجی نمونه ۱

10.000
40.000
50.000

ورودی نمونه ۲

4 2
1 2 10
1 3 20
1 4 30
1 2
3 4 

خروجی نمونه ۲

110.000
110.000

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