شهر تهران از $n$ محله و $n-1$ بزرگ‌راه دوطرفه تشکیل شده است که هرکدام از آن‌ها دو محله‌ی متفاوت را به یک‌دیگر متصل می‌کنند. همچنین تضمین می‌شود که بین هر دو محله‌ی دلخواه، یک مسیر با عبور از تعدادی بزرگ‌راه وجود دارد. مارکو به ایران سفر کرده و قصد دارد تا تمام محله‌های تهران را با ماشین کرایه‌ای خود بگردد و سپس با یکی از پروازهای ITA Airways به ونیز برگردد.

مارکو می‌داند به دلیل آنکه در رانندگی بسیار آدم بی‌توجه و کم‌احتیاطی است همیشه سرعت غیرمجاز بزرگ‌راه‌ها را زیرپا می‌گذارد و هربار که از یک بزرگ‌راه پلیس‌دار عبور کند جریمه می‌شود. او با توجه به نقشه‌ی راهنمایی و رانندگی تهران متوجه شده است که بزرگ‌راه $i$اُم بین دو محله‌ی $u_i$ و $v_i$ قرار دارد و جریمه‌ی عبور با سرعت غیرمجاز از آن برابر $w_i$ است.

مارکو از محله‌ی $s$ (سعادت‌آباد) بعد از کرایه‌ی ماشین، سفر خود را آغاز می‌کند و متوجه می‌شود که پلیس در بزرگ‌راه $t$اُم (همت) است. او هر مرحله می‌تواند با عبور از یکی از بزرگ‌راه‌های مجاور خود، به محله‌ی دیگری برود. پلیس نیز می‌تواند پس از حرکت مارکو، به یکی از بزرگ‌راه‌های مجاور¹ فعلی خود برود. می‌دانیم که پلیس هیچ‌گاه داخل یک محله نمی‌رود؛ یعنی مارکو تنها زمانی جریمه می‌شود که خودش وارد بزرگ‌راهی که پلیس درونش قرار دارد بشود. پلیس می‌تواند در یک مرحله جایگاه فعلی خود را حفظ کند و در محل خود باقی بماند، ولی مارکو از آنجا که برای برگشتن عجله دارد مجاز به انجام این کار نیست.

مارکو گردش خود را تا اولین لحظه‌ای که تمام محله‌های تهران را حداقل یک‌بار ببیند ادامه می‌دهد. او سعی دارد تا هزینه‌ی جریمه‌های خود را را کمینه کند و از این‌رو قصد دارد تا متوجه شود که اگر به بهترین شکل ممکن سعی کند تا تمام محله‌های تهران را حداقل یک‌بار ببیند، در بدبینانه‌ترین حالت چه مقدار جریمه باید پرداخت کند؟

¹دو بزرگراه مجاورند اگر و تنها اگر یک سر از هر دوی آن‌ها به یک محله یکسان متصل باشد.

خط اول به ترتیب شامل ۳ عدد $n$ و $s$ و $t$ است که نشان‌دهنده‌ی تعداد محله‌های تهران، محله‌ی اولیه‌ی مارکو (سعادت‌آباد)، و بزرگ‌راه اولیه‌ی پلیس (همت) است.

هرکدام از $n-1$ خط بعدی شامل اطلاعات بزرگ‌راه $i$اُم است که به ترتیب شامل ۳ عدد $u_i$ و $v_i$ و $w_i$ می‌شود که نشان‌دهنده‌ی یک بزرگ‌راه بین دو محله‌ی $u_i$ و $v_i$ با جریمه‌ی $w_i$ است.

تضمین می‌شود که از هر محله‌ی دلخواه $a$ به هر محله‌ی دلخواه دیگر $b$، یک مسیر با عبور از بزرگ‌راه‌های ورودی وجود دارد.

در خروجی شما باید یک عدد که نشان‌دهنده‌ی کم‌ترین هزینه‌ی جریمه‌های مارکو برای دیدن تمام $n$ محله‌ی تهران است را چاپ کنید.

• زیرمسئله اول (۷ نمره): گراف ورودی یک مسیر است
• زیرمسئله دوم (۶ نمره): پلیس در ابتدا داخل یک بزرگ‌راه مجاور محله‌ی اولیه‌ی مارکو است
• زیرمسئله سوم (۸ نمره): پلیس در ابتدا با طی کردن حداکثر یک گام می‌تواند به بزرگ‌راه مجاور محله‌ی اولیه‌ی مارکو برسد
• زیرمسئله چهارم (۲۴ نمره): $n \leq 20$
• زیرمسئله پنجم (۲۰ نمره): $n \leq 500$
• زیرمسئله ششم (۳۵ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 5\,000$
• $1 \leq s \leq n$
• $1 \leq t \leq n - 1$
• $1 \leq u_i, v_i \leq n$
• $1 \leq w_i \leq 10^9$

در مثال اول، حرکات مارکو و پلیس در هر مرحله به شکل زیر است. مارکو در انتها مجبور است حداقل به اندازه‌ی مجموع جریمه‌ی یال‌های سبز که برابر با $2+1+2+1=6$ است جریمه پرداخت کند.