+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- توی ماه مبارک رمضان ملت برای افطاری به خونه ی همدیگه میرن و خب مرسومه که یک جعبه شیرینی هم برای صاحب مجلس می برن. مش رمضون از این فرصت استفاده کرده و می خواد یک استارتاپ بزنه (با اون سنش خجالتم نمیکشه!!). شهر مش رمضون اینا $N$ تا خونه داره (که با 1 تا $N$ شماره گذاری شده اند) که خونه های 1 تا $K$ از این خونه ها شیرینی فروشی هستند. شهر مش رمضون اینا $M$ تا جاده ی یک طرفه داره که بین خونه ها کشیده شدن ولی از اونجایی که در این شهر کرونای منحوس هنوز وجود داره، تردد در هر یک از این جاده ها یک جریمه ای داره. (دولت برای کنترل کرونا در این شهر این کار رو انجام داده) و اما ایده ی مش رمضون: مش رمضون می خواد اپلیکیشنی طراحی کنه که مبدا و مقصد کاربر رو دریافت کنه و در صورت امکان مسیری رو بده که از مبدا شروع بشه، از یک شیرینی فروشی بگذره و سپس به مقصد برسه و طبعا کمترین جریمه رو داشته باشه. راستی بگم که شیرینی فروش هم دل داره و ممکنه خودش هم بخواد به خونه ی کسی بره، در این صورت دیگه لازم نیست به شیرینی فروشی دیگه ای بره و از مغازه ی خودش شیرینی می بره. از اون جایی که مش رمضون برنامه نویسی بلد نیست از شما خواسته که این برنامه رو برایش بنویسید و نتایجی رو براش به دست بیارید. توجه کنید که اگر اپلیکیشن مسیر مناسبی را برای کاربر پیدا نکند از او می خواهد که به این مهمانی نرود. # ورودی در خط اول به شما $N, M, K, Q$ داده می شود که به ترتیب تعداد شهر ها، تعداد جاده ها، تعداد شیرینی فروشی ها و تعداد در خواست های امروز است. در $M$ خط بعدی به شما وضعیت جاده ها داده می شود که $Ui$ مبدا، $Vi$ مقصد و $Ci$ میزان جریمه هستند و به ترتیب به شما داده می شوند. در $Q$ خط بعدی به شما ورودی کاربر ها داده می شود یعنی در هرکدام از این خط ها به شما دو عدد $ai$ و $bi$ داده می شود که به ترتیب مبدا و مقصد هر کاربر است. $$1 \le N \le 200$$ $$1 \le K \le 100$$ $$1 \le Q, M \le 10000$$ $$1 \le Ci \le 1000000$$ # خروجی شما باید دو عدد را در انتهای کار برای مش رمضون چاپ کنید، اول از همه تعداد کاربرانی را که بهشان پیشنهاد نکردید که به مهمانی نروند و سپس مجموع کل هزینه ای که کاربران دیگر با استفاده از اپلیکیشن شما پرداخته اند (تا مش رمضون بتونه با این داده ها از دولت پورسانت بگیره:))‌ ) ## ورودی نمونه ۱ ``` 3 3 1 3 3 1 10 1 3 10 1 2 7 3 2 2 3 1 2 ``` ## خروجی نمونه ۱ ``` 2 24 ```