* محدودیت زمان:‌ ٢ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ---------- سابیرا در کشور قزاقستان زندگی می‌کند. این کشور از $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\}$

حل سؤال در بانک سؤالات