• محدودیت زمان:‌ ٢ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • منبع: آزمون مقدماتی دوم دوره ۲۷ المپیاد کامپیوتر

سابیرا در کشور قزاقستان زندگی می‌کند. این کشور از nn شهر با شماره‌های 00 تا n1n-1 تشکیل شده‌است که با mm جاده دوطرفه به هم وصل شده‌اند. جاده‌ی ii-ام دو شهر uiu_i و viv_i را به هم وصل می‌کند. کریسمس نزدیک است و او می‌خواهد به قوم و خویش خود سر بزند.

او در شهر xx زندگی می‌کند؛ اقوام پدری او در شهر yy و اقوام مادری او در شهر zz زندگی می‌کنند. او می‌خواهد برای تعطیلات از شهر خود xx به شهر اقوام پدری yy و سپس به شهر اقوام مادری zz برود و در نهایت به خانه‌اش در شهر xx بازگردد.

به علت بارش سنگین برف و ناآشنا بودن سابیرا با جاده‌ها، عبور از جاده‌ی ii -ام برای بار اول aia_i دقیقه طول می‌کشد و بارهای بعد (مستقل از جهت حرکت روی جاده) bib_i دقیقه طول خواهد کشید (aibia_i \ge b_i).

سابیرا برای اینکه بیشتر در کنار اقوامش باشد می‌خواهد کمترین زمان را در جاده‌ها سپری کند. کمترین زمان سپری‌شده در جاده‌ها را پیدا کنید.

ورودی

در سطر اول ورودی دو عدد nn و mm آمده‌است.

در سطر بعد به‌ترتیب سه عدد xx، yy و zz آمده‌است.

در ii امین سطر از mm سطر بعدی به‌ترتیب چهار عدد uiu_i، viv_i، aia_i و bib_i آمده‌است. 3n5003 \le n \le 500 2mn×(n1)22 \le m \le \frac{n \times (n-1)}{2} 0x,y,z<n0 \le x, y, z < n 0ui,vi<n0 \le u_i, v_i < n 0biai1090 \le b_i \le a_i \le 10^9

هیچ جاده‌ای یک شهر را به خودش وصل نمی‌کند.

بین هر دو شهر حداکثر یک جاده‌است.

سه شهر xx و yy و zz متفاوت هستند.

تضمین می‌شود که مسیری از xx به yy و از xx به zz وجود دارد.

خروجی

در تنها سطر خروجی زمان کوتاه‌ترین سفر ممکن را چاپ کنید.

زیرمسئله‎ها

زیرمسئله نمره محدودیت
۱ ۱۴ بین هر دو شهری از nn شهر قزاقستان، دقیقا یک مسیر از جاده‌ها وجود دارد
۲ ۱۹ ai=bia_i = b_i
۳ ۶۷ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5 6
0 1 2
0 1 20 15
0 3 7 2
3 4 4 4
4 1 10 5
4 2 15 15
2 3 14 13
Plain text

خروجی نمونه ۱

57
Plain text

در مثال بالا، ترتیب پیمایش بهینه شهرها 0,3,4,1,4,2,3,0{0, 3, 4, 1, 4, 2, 3, 0}


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.