در شهر المپیادی‌ها مترو در دست شرکت‌های خصوصی می‌باشد. هر شرکت برای خود تعدادی خط مترو دارد (دقت کنید در این شهر خطوط مترو دو طرفه‌اند). این شهر دارای $n$ ایستگاه مترو می‌باشد که این خطوط بین این ایستگاه‌ها کشیده شده‌اند. یکی از دانش‌پژوهان قصد دارد از ایستگاه $s$ که خانه او در آن‌جا قرار دارد به ایستگاه $t$ که باشگاه دانش‌پژوهان جوان در آن‌جا قرار دارد برود. مشکل او پیچیدگی‌ای می‌باشد که در متروی این شهر وجود دارد. برای استفاده از خطوط هر شرکت به این صورت عمل می‌شود: شرکت مورد نظر مبلغی را به عنوان ورودی می‌گیرد و ما می‌توانیم از خطوط این شرکت استفاده کنیم به شرطی که در این حین از خطوط شرکت دیگری استفاده نکنیم. اگر از خطوط شرکت دیگری استفاده کنیم برای استفاده مجدد از خطوط شرکت اول باید دوباره مبلغ ورودی را بپردازیم. پس از ورود، استفاده از هر خط مترو که دو ایستگاه را به هم متصل می‌کند، هزینه‌ای دارد که در صورت استفاده باید این مبلغ را نیز بپردازیم. مثلا فرض کنید شهر ما ۴ ایستگاه دارد و دو شرکت که شرکت اول دو ایستگاه ۱ و ۲ و همچنین دو ایستگاه ۳ و ۴ را به هم متصل می‌کند و شرکت دوم دو ایستگاه ۲ و ۳ را به هم وصل می‌کند. گر این فرد بخواهد از ایستگاه ۱ به ۴ برود باید هزینه ورودی شرکت اول را بپردازد، سپس (با پرداخت هزینه‌ی خط) از خط مترو به ایستگاه ۲ برود، سپس ورودی شرکت دوم را بپردازد و به ایستگاه ۳ برود، در آخر دوباره ورودی شرکت ۱ را بپردازد و به ایستگاه ۴ برود.

به این دانش‌پژوه کمک کنید تا بتواند با صرف کم‌ترین هزینه از خانه به باشگاه بیاید.

برنامه‌ای بنویسید که:

• ساختار و هزینه‌های خطوط مترو و شرکت‌ها را از ورودی بخواند.
• کم‌هزینه‌ترین روش برای رفتن از مبدا به مقصد را محاسبه کنید.
• این روش را در خروجی بنویسید.

در سطر اول ورودی، $s،k،n$ و $t$ آمده است که به ترتیب تعداد ایستگاه‌های مترو، تعداد شرکت‌های خصوصی، ایستگاه مبدا و ایستگاه مقصد هستند. ($1\leq n,k \leq 250$ و ایستگاه‌ها با ۱ تا $n$ و شرکت‌های مترو نیز با ۱ تا $k$ شماره‌گذاری شده‌اند و تمام اعداد ورودی، صحیح، نامنفی و کم‌تر از $10^6$ می‌باشند.)

در سطر دوم، $k$ عدد آمده است که عدد $i$ام، هزینه‌ی ورودی شرکت $i$ام را مشخص می‌کند. سپس ورودی به $k$ دسته تقسیم می‌شود که هر دسته به صورت زیر است:

دسته‌ی $i$ام، خطوط شرکت $i$ام را مشخص می‌کند. در ابتدا، $e_i$، تعداد خطوط این شرکت آمده است. در هر یک از $e_i$ سطر بعد از آن، ۳ عدد $u$ و $v$ و $c$ آمده است که مشخص می‌کند ایستگاه $u$ به $v$ وصل شده است و در صورت استفاده از این خط باید مبلغ $c$ تومان به شرکت $i$ام پرداخته شود. دقت کنید ممکن است که یک شرکت چندین خط بین یک جفت ایستگاه داشته باشد.

در صورت وجود مسیر، در سطر اول خروجی دو عدد $o$ و $l$ بنویسید که $o$ کم‌ترین مقدار پول مورد نیاز برای رسیدن به باشگاه است و $l$ تعداد خطوط مورد استفاده را مشخص می‌کند.

در هر یک از $l$ سطر بعد، دو عدد $x$ و $y$ به این معنی بنویسید که به ایستگاه $x$ توسط شرکت $y$ می‌رویم.

در صورتی که مسیری به مقصد وجود نداشت، در تنها سطر خروجی، تنها یک $-1$ بنویسید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۴۰۰ مگابایت

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