• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر

---

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

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

ورودی

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

هر کدام از $m$ سطر بعدی شامل سه عدد طبیعی $u$ و $v$ و $p$ است که به معنای وجود یک جاده‌ی دوطرفه با احتمال مسدود بودن $p/1000$ بین دو شهر $u$ و $v$ است.

تضمین می‌شود که گراف شهر‌های داده‌شده همبند است.

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

احتمال مسدود بودن تمامی جاده‌ها کمتر از ۱ است.

$$ 2 \le n \le 100\ 000$$ $$ 1 \le m \le 100\ 000$$ $$ 1 \le u , v \le n $$ $$ u \ne v$$ $$ 0 \le p \le 1\ 000$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۵	گراف شهر‌ها درخت است.
۲	۵۵	$ n \le 1\ 500 $ و حداکثر چهار جاده به هر شهر وصل است
۳	۱۵	$ n \le 300 $
۴	۲۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 4
1 2 500
1 3 500
2 4 625
3 4 500

خروجی نمونه ۱

3.556

ورودی نمونه ۲

2 1
1 2 999

خروجی نمونه ۲

1000.000

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