دو دوست که اکنون در مدرسه‌شان هستند، می‌خواهند به خانه‌هایشان بروند. از آن‌جایی که آن دو تنبل هستند، می‌خواهند از مسیری به خانه بروند که کم‌ترین مسافت را طی کنند. ولی به خاطر دوستی‌شان می‌خواهند که بیش‌ترین زمان ممکن را هم در کنار هم باشند. چه کنیم که وقتشان از دوستی‌شان مهم‌تر است (یعنی حاضر نیستند که مسیرشان را طولانی بکنند). حال باید بهترین مسیر را برای آن‌ها پیدا کنید. آن‌ها در شهری زندگی می‌کنند که شامل یک سری میدان و یک سری خیابان است و هر خیابان دو میدا را به هم وصل می‌کند و البته هر خیابان طولی دارد. خیابان‌ها دو طرفه هستند. از نکات جالب در این شهر این‌که مدرسه‌ی دو دوست و خانه‌هایشان در وسط میدان‌ها واقع شده‌اند! شما باید با دانستن اطلاعات خیابان‌ها و میادین و محل مدرسه و دو خانه، بهترین مسیرها را بیابید. (توجه کنید که $1\leq n \leq 1000$ )

در سطر اول فایل ورودی عدد $n$ (تعداد میادین) و سه عدد $s$، $a$ و $b$ آمده‌اند که به ترتیب شماره‌ی میادینی هستند که مدرسه و خانه‌ی دو دوست در آن‌ها واقع‌اند. سپس در $n$ سطر و در هر سطر $n$ عدد صحیح نامنفی آمده که عدد $j$ ام در سطر $i$ ام آن اگر صفر باشد، نشان‌دهنده‌ی این است که بین دو میدان $i$ و $j$ خیابیانی وجود ندارد وگرنه طول خیابان بین دو میدان $i$ و $j$ را نشان می‌دهد.

در سطر اول فایل خروجی، شما باید به ترتیب طول مسیری که نفر اول و نفر دوم طی می‌کنند و سپس طول مسیر مشترک را بنویسید. در سطر بعد یک عدد که تعداد رئوس مسیر نفر اول است و سپس رئوس آن مسیر را به ترتیب بنویسید. در سطر بعد یک عدد که تعداد رئوس مسیر نفر دوم است و سپس رئوس آن مسیر را به ترتیب بنویسید.

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