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

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

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

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

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

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

• $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 10^6$

در ورودی نمونه‌ی اول، از هر شهر تنها یک پرواز خروجی داریم. بنابراین حرکات مدکا یکتاست. او بعد از $2$، $5$، $8$، $11$، $14$، $17$، … پرواز به دانشگاهش می‌رسد. زودترین زمانی که می‌تواند به دانشگاهش برسد به طوری که تعداد پرواز‌ها بر $k=7$ بخش‌پذیر باشد، بعد از $14$ پرواز است که با توجه به زمان پرواز‌ها، دقیقا $14$ واحد زمانی طول می‌کشد.

در ورودی نمونه‌ی دوم، با توجه به این‌که از هر شهر تنها یک پرواز خروجی داریم، حرکات مدکا یکتاست و با توجه به پرواز‌ها تنها بعد از $3x+2$ ($0\leq x$) پرواز مدکا می‌تواند به دانشگاهش برسد. در تنیجه مدکا به هیچ صورتی نمی‌تواند به هدفش برسد.

در ورودی نمونه‌ی سوم، مدکا می‌تواند با طی کردن پروازهای یکم، چهارم، پنجم، چهارم، پنجم و در آخر پرواز دوم به دانشگاهش برسد.

• سوال بعد