سوال ۳

زمستان سردی است و بارش سنگین برف، باعث مسدود شدن را‌ه‌ها شده‌ است. آقای مهندس برای یک پروژه‌ی کاری به شهر $1$ رفته و قصد دارد به خانه‌اش که در شهر شماره‌ی $n$ قرار دارد باز‌گردد. او در هر روز می‌تواند در شهری که هست بماند و یا یکی از جاده‌های غیر‌مسدود متصل به آن شهر را طی کند. آقای مهندس اطلاعات بسیار مفیدی از سازمان‌ هواشناسی کسب کرده و احتمال مسدود بودن هر جاده را می‌داند. دقت کنید که مسدود بودن یک جاده در یک روز، مستقل از مسدود بودن یا نبودن آن، در روز‌های قبل‌اش است. برای نمونه، اگر احتمال مسدود بودن یک جاده را $p$ بگیریم، احتمال این که جاده دو روز متوالی مسدود باشد، $p^2$ و احتمال این‌که در هیچ‌کدام از دو روز بسته نباشد، $(1-p)^2$ است. عبور از هر جاده دقیقا یک روز طول می‌کشد.

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

• در سطر اول ورودی دو عدد طبیعی $n$، تعداد شهر‌ها، و $m$، تعداد جاده‌ها، آمده است.
• هر کدام از $m$ سطر بعدی شامل سه عدد طبیعی $u$ و $v$ و $p$ است که به معنای وجود یک جاده‌ی دوطرفه با احتمال مسدود بودن $p/1000$ بین دو شهر $u$ و $v$ است.
• تضمین می‌شود که گراف شهر‌های داده‌شده همبند است.
• بین هر دو شهر حداکثر یک جاده وجود دارد و هیچ‌ شهری به خودش جاده ندارد.
• احتمال مسدود بودن تمامی جاده‌ها کمتر از $۱$ است.
• $2 \leq n \leq 10^5$
• $1 \leq m \leq 10^5$
• $1 \leq u, v \leq n, u \neq v$
• $0 \leq p < 1000$

در تنها سطر خروجی امید‌ریاضی تعداد روز‌هایی که آقای مهندس در راه است را با دقیقا $۳$ رقم اعشار چاپ کنید.

• زیرمسئله اول (۵ نمره): گراف شهر‌ها به شکل درخت است.
• زیرمسئله دوم (۵۵ نمره): حداکثر چهار جاده به هر شهر متصل است و $n \leq 1500$
• زیرمسئله سوم (۱۵ نمره): $n \leq 300$
• زیرمسئله چهارم (۲۵ نمره): بدون محدودیت اضافی

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

• سوال قبل