در یک دهکده‌ی دورافتاده، ‎$n$‎ کلبه وجود دارد که بین برخی از آن‌ها جاده‌ی قابل عبور (دو طرفه) احداث شده است. در هر کلبه دقیقاً یک پیرمرد نجّار زندگی می‌کند. با توجه به هزینه‌ی ساخت جاده، جاده‌های این دهکده طوری ساخته شده‌اند که بین هر دو کلبه تنها یک مسیر (دنباله از جاده‌ها) وجود داشته باشد. ‎

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

طبق یک آئین سنّتی دیگر، افراد دهکده باید یک زمانی را بین خودشان تنظیم کنند و دقیقاً در آن لحظه، همه ساکنین (هر کدام دقیقاً در خانه‌ی خودش) هم‌زمان دعای مخصوص سال نو را بخوانند. برای افراد دهکده خیلی مهم است که زمان خواندن دعا در سریع‌ترین زمان ممکن اتفاق بیافتد. منتهی همان‌طور که گفته شد، شیوه‌ی اطلاع‌رسانی در این دهکده به‌صورت شفاهی است. بهعبارت دقیق‌تر هر کس که از رویداد مطلع شود، می‌تواند دقیقاً یکی از جاده‌های متّصل به کلبه‌اش را طی کند تا به کلبه‌ی انتهای دیگر جاده برسد؛ بعد صاحب آن کلبه را از رویداد مطلع کند و در پایان بلافاصله به خانه‌اش برگردد. پس از بازگشت به خانه، در صورت لزوم، آن شخص می‌تواند پیش یکی دیگر از همسایه‌هایش برود و برگردد و … ‎

دقت کنید که ساکن کلبه‌ی ‎$X$‎، تنها می‌تواند پیش همسایگان خود (کلبه‌هایی که با یک جاده به کلبه‌اش متصل‌اند) برود و نه دورتر از آن. نکتهی قابل تأمل برای ‎$X$‎، ترتیبِ رفتن به همسایه‌هایش است چرا که هم طول جاده‌ها و هم تعداد افراد دیگری که خودِ همسایه‌های ‎$X$‎ باید آن‌ها را باخبر کنند، و نهایتاً خبر رسانی سایرین در تصمیم‌گیری ‎$X$‎ مؤثر است. به‌یاد داشته باشید که هیچ‌کس پیش از مطلع شدن از خبر سال نو، از کلبه‌اش خارج نمی‌شود. هم‌چنین در زمان تنظیم شده برای نیایش، همه افراد باید در خانه خودشان باشند‎.

اکنون با اطلاع از ساختار دهکده و کلبه‌های ‎حسام دست‌چکّش‎ و ‎سعید سمباده، این دو نجّار از شما می‌خواهند که یک برنامه‌ریزی عمومی برای نحوه اطلاع‌رسانی تک تک افراد دهکده ارائه دهید تا لحظه‌ی نیایش در زودترین زمان ممکن (از شروع شنیده شدن آواز عرفانی) اتفاق بیافتد.

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

• از ورودی‎ تعداد کلبه‌ها ‎($n$)‎، تعداد جاده‌ها ‎($e$)‎، شماره‌ی کلبه‌ی حسام دست‌چکّش‎‎ و شماره‌ی کلبه‌ی ‎سعید سمباده‎ را بخواند.
• برای هر جاده، شماره‌ی کلبه‌های دو سرش و طول آن جاده را بخواند. فرض کنید طول‌ها به متر و سرعت همه افراد یک متر در ثانیه است.
• با تنظیم یک برنامه‌ریزی فرد به فرد، سریع‌ترین مدّت زمانی که تمامی افراد دهکده می‌توانند از رویداد باخبر شده و به خانه خودشان برگشته باشند را محاسبه کرده و این مدّت زمان را در ‎خروجی‎ بنویسد.

• در سطر اول ورودی، ابتدا عدد ‎$n$‎ و سپس عدد ‎$e$‎ قرار دارد‎.‎
• در سطر دوم ورودی، شماره کلبه‌ی ‎حسام دست‌چکّش‎‎ ($S_1$) ‎ و شماره‌ی کلبه‌ی ‎‎سعید سمباده ($S_2$)‎ قرار دارد.‎
• سطر سوم تا ‎$(e+2)$‎اُمِ ورودی، جاده‌ها را توصیف می‌کنند به این نحو که در هر خط سه عدد ‎$v_1 \ v_2 \ w$‎ نوشته می‌شود که دو عدد اوّل شماره کلبه‌های دو سر جاده و عدد سوم ‎($w$)‎ طول جاده است.
• فرض کنید دو سر جاده‌ها با هم متفاوت بوده و جاده‌ی تکراری نداریم. طول جاده‌ها حداکثر هزار متر است.
• شماره کلبه‌ها از ‎۱‎ تا ‎$n$‎ است و بالطّبع ‎$1\le (S_1 \ne S_2) \le n$‎.
• ‎$2 \le n‎, ‎e \le 100~000$‎

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

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

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

‎