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

در قریب‌آباد $n$ میدان و $m$ خیابان یک‌طرفه وجود دارد. هر خیابان از یک میدان آغاز و به یک میدان دیگر ختم می‌شود و در میانه‌ی راه از میدان دیگر ی نمی‌گذرد و با خیابان دیگری تقاطع ندارد. البته ممکن است خیابان‌ها با پل از روی یک‌دیگر رد شوند ولی فقط در تقاطع‌ها به هم راه دارند. بین هر دو میدان $A$ و $B$، حداکثر یک خیابان از $A$ به $B$ و حداکثر یک خیابان از $B$ به $A$‌وجود دارد. بالطبع، بین هر دو میدانی لزوما خیابان وجود ندارد.

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

وقتی یک راننده از اهالی قریب‌آباد بخواهد از مبدا به سمت مقصد حرکت کند، در هر میدان (از جمله میدان مبدا) برای ادامه‌ی راه خود، خیابانی را انتخاب می‌کند که او را با کوتاه‌ترین مسیر ممکن به مقصد می‌رساند (هر خیابان یک طول دارد و طول یک مسیر، مجموع طول خیابان‌های آن است). ممکن است راننده در هنگام حرکت به میدانی برسد که برای حرکت در کوتاه‌ترین مسیر، چند انتخاب داشته باشد و خیابان‌های متعددی او را با کوتاه‌ترین مسیر به مقصد برساند. در چنین شرایطی، اگر $k$ خیابان از آن میدان برای ادامه‌ی کوتاه‌ترین مسیر موجود باشد، راننده به صورت تصادفی و با احتمال مساوی (برابر با $\frac{1}{k}$) یکی از خیابان‌ها را انتخاب می‌کند و مسیر خود را از طریق آن ادامه می‌دهد. ممکن است این اتفاق در طول مسیر چندین‌بار رخ دهد و هر دفعه که راننده با چنین شرایطی مواجه می‌شود یکی از خیابان‌ها را به صورت تصادفی انتخاب کند. هم‌چنین ممکن است برای راننده‌ای چنین شرایطی در هیچ یک از میدان‌های در طول مسیر، پیش نیاید.

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

برنامه‌ای بنویسید که:

• ساختار راه‌های شهر و آمار حرکت شهروندان را از ورودی بخواند.
• متوسط تعداد ماشین‌هایی که در یک روز ازهر خیابان رد می‌شوند را محاسبه کند.
• مقادیر محاسبه شده را در خروجی بنویسد.

• در سطر اول ورودی، دو عدد طبیعی $n$ و $m$ قرار دارد.($0<n\leq 100$ و مجموع تعداد کل ماشین ها (در $n$ خط آخر ورودی) از $10^5$ بیش‌تر نیست).
• در هر یک از $m$ سطر بعد، مشخصات یک خیابان با سه عدد طبیعی $b،a$ و $l$ داده می‌شود که نشان‌دهنده‌ی یک خیابان یک‌طرفه با طول $l$ از میدان $a$ به میدان $b$ است. میدان‌ها با $1,2,…,n$ شماره‌گذاری شده‌اند.
• در هر یک از $n$سطر بعد، $n$ عدد صحیح نامنفی آمده است. عدد $j$ام از سطر $i$ام در این بخش،‌متوسط تعداد ماشین‌هایی درهر روز را نشان می‌دهد که حرکت خود را از میدان $i$ شروع می‌کنند و در میدان $j$ به پایان می‌رسانند. این عدد تنها زمانی بزرگ‌تر از صفر است که از میدان $i$ به میدان $j$ مسیری وجود داشته باشد. عدد $i$ام از سطر $i$ام در این بخش نیز همیشه برابر صفر است(مبدا و مقصد هیچ راننده‌ای یک میدان نیست).
• اعداد هر سطر با فاصله از هم جدا شده‌اند.

خروجی را در $m$ سطر بنویسید. در سطر $i$ام، متوسط تعداد ماشین‌هایی را در هر روز بنویسید که از خیابان $i$ام ورودی عبور می‌کنند. تنها در صورتی به خروجی نمره تعلق می‌گیرد که اختلاف هر عدد آن با پاسخ در ست حداکثر $10^{-2}$ باشد.

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

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