مسابقه برنامه نویسی

سایت بیان یه مسابقه برنامه نویی گذاشت

من از این سوالش خیلی خوشم اومدش

البته جوابش تو سایتش هست

بشکه‌های آب

n بشکه‌ی آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود می‌باشد که با عددی یکتا بین 1 تا n شماره گذاری شده است. i-امین لوله بشکه‌ی x​i​​ و y​i​​ را به هم متصل می‌کند. یک سر این لوله در ارتفاع h​i​​ متر به بشکه‌ی x​i​​ متصل است و سر دیگر آن در همان ارتفاع به بشکه‌ی y​i​​ متصل است. در زمان 0‌ بشکه‌ها خالی می‌باشند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت، در بشکه‌ی 1 می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه‌های دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.

شما باید برای هر بشکه اولین زمانی را حساب کنید که آب وارد آن می‌شود.

ورودی

در سطر اول ورودی عدد صحیح T، تعداد تست‌ها آمده‌است. پیش از هر تست، یک سطر خالی آمده‌است. برای هر تست در یک سطر ورودی اعداد n نشان دهنده‌ی تعداد بشکه‌ها و m نشان دهنده‌ی تعداد لوله‌ها را بخوانید. سپس در m سطر بعدی در هر سطر اعداد x​i​​ و y​i​​ و h​i​​ آمده است، که به ترتیب نشان دهنده‌ی بشکه‌ی دو سر لوله و ارتفاع نقطه‌ی اتصال هر انتهای آن است. می‌دانیم برای هر بشکه زمانی وجود دارد که آب وارد آن بشکه می‌شود.

• 1≤T≤100
• 1≤n≤1000
• n−1≤m≤1000
• x​i​​≠y​i​​
• 1≤h​i​​≤10​6​​
• تمام h​i​​ ها متمایز اند.

خروجی

به ازای هر تست، ابتدا یک سطر شامل Case #x: بنویسید، که در آن x نشان‌دهنده‌ی شماره‌ی تست است، با شروع از 1. در سطر بعدی n عدد را با فاصله از هم چاپ کنید. i-امین عدد، زمانیست که آب برای اولین بار وارد بشکه‌ی i می‌شود.

ورودی نمونه

3

2 1
1 2 10

3 2
1 2 10
2 3 20

3 3
1 2 10
2 3 20
1 3 15

خروجی نمونه

Case #1:
0 10
Case #2:
0 10 40
Case #3:
0 10 30