Lonely Mohsen

Time Limit: 5 Seconds    Memory Limit: 131072 KB

از وقتی که معین برای تحصیل علم و شرکت در همه کلاس‌های دانشگاهش و گرفتن نمره‌های عالی به تهران آمده محسن هم دیگر هم بازی(!) ندارد. او برای این که حوصله اش سر نرود بازی زیر را به تنهایی برای خودش انجام می‌دهد. او تعدادی بشکه با سطح مقطع یک و ارتفاع بی نهایت را با تعدادی لوله به هم وصل می‌کند به این شکل که یک سر لوله i ام در ارتفاعh_i  به یکی از بشکه‌ها و سر دیگر آن نیز در همان ارتفاع به بشکه دیگری متصل است.در لحظه 0 همه بشکه‌ها خالی هستند . شیر آب بالای بشکه شماره یک قرار دارد و در لحظه صفر محسن آن را باز می‌کند تا با سرعت یک متر مکعب بر ساعت در بشکه شماره یک آب ریخته شود. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد آب در آن لوله جریان پیدا می‌کند و می‌تواند وارد بشکه‌های دیگر شود فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است. برای او جالب است که بداند برای هر بشکه اولین لحظه‌ای که آب به آن بشکه وارد می‌شود چه زمانی است؟(محسن طوری بشکه‌ها را به هم متصل کرده که برای هر بشکه زمانی وجود داشته باشد که به آن آب وارد شود.)

او به تنهایی نمی‌تواند این سوال را حل کند و سوالش را برای معین مطرح می‌کند. معین هم چون حوصله حل سوال را ندارد این کار را به شما محول می‌کند. شما باید برای هر بشکه اولین زمانی را حساب کنید که آب به آن وارد می‌شود.

Input

در سطر اول ورودی عدد صحیح T، تعداد تست‌‌ها آمده‌است. پیش از هر تست، یک سطر خالی آمده‌است. برای هر تست در یک سطر ورودی اعداد n نشان دهنده‌ی تعداد بشکه‌ها و m نشان دهنده‌ی تعداد لوله‌ها را بخوانید. سپس در m سطر بعدی در هر سطر اعداد  x_i , y_i , h_i  آمده است، که به ترتیب نشان دهنده‌ی بشکه‌ی دو سر لوله و ارتفاع نقطه‌ی اتصال هر انتهای آن است.

تعداد تست‌ها در هر ورودی حداکثر ۱۰۰ تاست و تعداد بشکه‌هاو لوله‌های هر تست حداکثر ۱۰۰۰ تاست. می‌دانیم دو سر لوله به دو بشکه متفاوت متصل است و ارتفاع لوله‌ها حداکثر ۱۰^۶ است.

Output

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

Sample Input

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

Sample Output

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

Submit