DA-F94-CA4-2

Time Limit: 1 Second    Memory Limit: 65536 KB

در سرزمين نارنيا V شهر وجود دارد. بين شهر هاي نارنيا جاده هايي یک طرفه با عوارضي هاي مختلف و بعضا عجيب وجود دارد. اگر بين شهر i و j جاده اي وجود داشته باشد و عوارض اين جاده w باشد به اين معناست كه براي گذر از اين جاده بايد w واحد پولي پرداخت كرد. توجه داشته باشيد كه در سرزمين نارنيا w ميتواند عددي منفي باشد، به اين معنا كه اگر از آن جاده عبور كنيد به شما پول داده ميشود! حال شما بايد به ازاي هر دو شهر در نارنيا مقدار كمترين پولي را كه بايد براي سفر از شهر اول به شهر دوم پرداخت كرد، بدست آوريد توجه داشته باشيد كه پيچيدگي زماني الگوريتم شما بايد در بدترين حالت و "نه در همه حالات" برابر با V به توان سه باشد و استفاده از الگوريتم فلويد وارشال "مجاز نيست"

Input

ورودی شامل بلوک هاییست که هر بلوک ورودی به شرح زیر میباشد: خط اول هر بلوک يك عدد int مثبت معادل V (تعداد شهر ها) ميباشد( V برابر صفر به معنای پایان ورودی است ) و در V خط بعد اطلاعات مربوط به V شهر وجود دارد به طوري كه در خط L+1 ام هر بلوک اطلاعات مربوط به شهر L قرار دارد. خط ها نيز به اين صورت اند كه در اول خط i+1 ام هر بلوک عدد E وجود دارد كه نشان دهنده تعداد جاده هاي خارج شده از راس i ام ميباشد و در ادامه 2*E عدد وجود دارد كه دوتا دوتا به ترتيب معادل "شهر مقصد هر جاده و ميزان عوارض آن جاده" است. (ميتوانيد فرض كنيد ورودي دور منفي ندارد)

Output

خروجی شامل بلوک هایی است که توسط یک خط خالی از هم جدا شده اند، ( بعد از هر بلوک یک خط خالی وجود دارد ) هر بلوک خروجي متناسب با ورودی متناظر شامل V خط است و هر خط نيز شامل V عدد است به طوري كه "عدد j ام در خط i ام معادل كمترين مقدار پولي است كه براي سفر از شهر i به شهر j بايد پرداخت نمود”. (اگر از شهر i به شهر j هيچ مسيري وجود نداشت در ماتريس مجاورت خروجي در خط i ام و ستون j ام كمترين مقدار پول لازم براي سفر از i به j را inf چاپ كنيد)

Sample Input

2
1 2 -1
1 1 3
3
1 2 -1
1 3 1
0
0

Sample Output

0 -1
3 0

0 -1 0
inf 0 1
inf inf 0

Submit