- محدودیت زمان: ٢ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون مقدماتی دوم دوره ۲۷ المپیاد کامپیوتر
سابیرا در کشور قزاقستان زندگی میکند. این کشور از \(n\) شهر با شمارههای \(0\) تا \(n-1\) تشکیل شدهاست که با \(m\) جاده دوطرفه به هم وصل شدهاند. جادهی \(i\)-ام دو شهر \(u_i\) و \(v_i\) را به هم وصل میکند. کریسمس نزدیک است و او میخواهد به قوم و خویش خود سر بزند.
او در شهر \(x\) زندگی میکند؛ اقوام پدری او در شهر \(y\) و اقوام مادری او در شهر \(z\) زندگی میکنند. او میخواهد برای تعطیلات از شهر خود \(x\) به شهر اقوام پدری \(y\) و سپس به شهر اقوام مادری \(z\) برود و در نهایت به خانهاش در شهر \(x\) بازگردد.
به علت بارش سنگین برف و ناآشنا بودن سابیرا با جادهها، عبور از جادهی \(i\) -ام برای بار اول \(a_i\) دقیقه طول میکشد و بارهای بعد (مستقل از جهت حرکت روی جاده) \(b_i\) دقیقه طول خواهد کشید (\(a_i \ge b_i\)).
سابیرا برای اینکه بیشتر در کنار اقوامش باشد میخواهد کمترین زمان را در جادهها سپری کند. کمترین زمان سپریشده در جادهها را پیدا کنید.
ورودی
در سطر اول ورودی دو عدد \(n\) و \(m\) آمدهاست.
در سطر بعد بهترتیب سه عدد \(x\)، \(y\) و \(z\) آمدهاست.
در \(i\) امین سطر از \(m\) سطر بعدی بهترتیب چهار عدد \(u_i\)، \(v_i\)، \(a_i\) و \(b_i\) آمدهاست. \[3 \le n \le 500\] \[2 \le m \le \frac{n \times (n-1)}{2}\] \[0 \le x, y, z < n\] \[0 \le u_i, v_i < n\] \[0 \le b_i \le a_i \le 10^9\]
هیچ جادهای یک شهر را به خودش وصل نمیکند.
بین هر دو شهر حداکثر یک جادهاست.
سه شهر \(x\) و \(y\) و \(z\) متفاوت هستند.
تضمین میشود که مسیری از \(x\) به \(y\) و از \(x\) به \(z\) وجود دارد.
خروجی
در تنها سطر خروجی زمان کوتاهترین سفر ممکن را چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۴ | بین هر دو شهری از \(n\) شهر قزاقستان، دقیقا یک مسیر از جادهها وجود دارد |
| ۲ | ۱۹ | \(a_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
خروجی نمونه ۱
57
در مثال بالا، ترتیب پیمایش بهینه شهرها \(\{0, 3, 4, 1, 4, 2, 3, 0\}\)