سلطان و سلطانه به تازگی با هم ازدواج کرده‌اند. این دو یک‌دیگر را در سلطان‌آباد گم کردند. سلطان‌آباد $n$ شهر دارد که برخی از آن‌ها با جاده‌ی ۲ طرفه به هم وصل هستند. طول هر جاده نیز یک عدد طبیعی است. سلطان در شهر $X$ قرار دارد و سلطانه در شهر $Y$ گم شده است. سلطان می‌خواهد به شهر $Y$ برود و خانومش را پیدا کند. از آن‌جایی که این دو به تازگی ازدواج کرده‌اند و با وضع بسیار متعادل دلار، بدیهی است که این دو ماشین دارند، اما در پارکینگ است!

سلطان تصمیم می‌گیرد از تاکسی استفاده کند. در هر شهر یک تاکسی وجود دارد. راننده‌ی تاکسی شهر $i$، می‌تواند سلطان را از شهر $i$ به شهری دیگر با فاصله‌ی حداکثر $t_i$ ببرد. (فاصله‌ی دو شهر، برابر با طول کوتاه‌ترین مسیر وزن‌دار بین آن دو شهر است). هزینه‌ی تاکسی شهر $i$ نیز، ربطی به مسیر طی شده ندارد و برابر با $c_i$ است. هر تاکسی حداکثر یک‌بار می‌تواند استفاده شود. امکان پیاده شدن، فقط در شهرها وجود دارد و وسط جاده‌ها نمی‌توان پیاده شد. کمینه‌ی هزینه‌ای که سلطان برای رسیدن به معشوقش نیاز دارد، چقدر است؟

• در خط اول ورودی $n$ (تعداد شهرها) و $m$ (تعداد جاده‌ها) داده می‌شود.
• در خط دوم دو عدد $X$ و $Y$ به ترتیب داده می‌شوند که نماینگر شهر اولیه‌ی سلطان و شهری که سلطانه در آن است، می‌باشند.
• در هر یک از m خط بعد ۳ عدد $u_i$ و $v_i$ و $w_i$ داده می‌شود که به ترتیب دو شهر پایانی جاده‌ی $i$ ام و طول آن هستند.
• در هر یک از $n$ خط بعد نیز عدد $t_i$ و $c_i$ داده می‌شود.
• $1 \leq n, m \leq 1000$

• کمینه‌ی هزینه‌ی مورد نیاز سلطان را چاپ کنید.
• اگر سلطان نتواند به معشوقه‌اش برسد، او را طلاق می‌دهد و شما باید در خروجی ۱$-$ چاپ کنید.

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

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