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

---

تعطیلات تابستانی تمام شده و «مُدکا» باید از خانه به دانشگاه‌ برگردد. کشوری که مدکا در آن زندگی می‌کند شامل $n$ شهر است که با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند. خانه‌ی مدکا در شهر شماره‌ی ۱ و دانشگاهش در شهر شماره‌ی $n$ قرار دارد. او برای رفتن از خانه به دانشگاه می‌خواهد از هواپیما استفاده کند. همان‌طور که از نام او مشخص است، باقی‌مانده‌‌ی اعداد بر $k$ برای او مهم است، به همین دلیل او می‌خواهد تعداد پرواز‌هایی که برای رسیدن به دانشگاه انجام می‌دهد، بر $k$ بخش‌پذیر باشد. در عین‌حال او قصد دارد هر چه زودتر به دانشگاهش برسد، برای همین می‌خواهد مجموع زمان پرواز‌هایش در بین تمامی حالت‌هایی که تعداد پرواز‌هایشان بر $k$ بخش‌پذیر است، کمینه باشد. دقت کنید که مدکا می‌تواند از یک پرواز بیش از یک‌بار استفاده کند. هم‌چنین ممکن است او در بین راه نیز به شهر دانشگاهش برسد ولی چون تعداد پرواز‌هایش بر $k$ بخش‌پذیر نیست، به پرواز‌هایش ادامه دهد تا به هدفش برسد.

شما باید برنامه‌ای بنویسید که با گرفتن اطلاعات مربوط به پرواز‌ها و عدد $k$، کم‌ترین زمان رسیدن مدکا از خانه به دانشگاه را مشخص کند به شرطی که تعداد این پرواز‌ها بر $k$ بخش‌پذیر باشد. در صورتی که این کار امکان‌پذیر نباشد، برنامه‌ی شما باید عدد $-1$ را به عنوان جواب در نظر بگیرد.

ورودی

در سطر اول ورودی سه عدد صحیح $n$، تعداد شهر‌ها، $m$، تعداد پرواز‌ها، و $k$ آمده است.

در هر یک از $m$ سطر بعدی به ترتیب سه عدد طبیعی $u$، ‌$v$ و $t$ آمده است که نشان‌دهنده یک پرواز از شهر $u$ به $v$ در $t$ واحد زمان است. دقت کنید که پرواز‌ها یک طرفه‌ هستند.

$$2 \leq n \leq 200$$ $$0 \leq m \leq {n \times (n - 1)}$$ $$1 \leq k \leq 10^9$$ $$1 \leq u,v \leq n, u \neq v$$ $$1 \leq t \leq 1\ 000\ 000$$

خروجی

در تنها سطر خروجی پاسخ مسئله را چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۴	$ k \le 200 $
۲	۲۲	از هر شهر دقیقا یک پرواز خارج می‌شود.
۳	۶۴	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 3 7 
1 2 1 
2 3 1 
3 1 1

خروجی نمونه ۱

14

ورودی نمونه ۲

3 3 3 
1 2 10 
2 3 20 
3 1 30

خروجی نمونه ۲

-1

ورودی نمونه ۳

4 5 3 
1 2 10 
2 4 20 
4 1 30 
2 3 40 
3 2 50

خروجی نمونه ۳

210