قرار است هیئتی از نمایندگان یک کشور برای انجام مذاکراتی به کشور شما بیاید. این افراد در ابتدا در کشور شماره ۱ قرار دارند و با استفاده از هواپیمای مخصوص خود به کشور شما می‌آیند. متاسفانه بین همه کشورها خط هوایی وجود ندارد، به همین دلیل این هیئت لازم دارد برای رسیدن به کشور شما از تعدادی از خطوط هوایی بین کشورها استفاده کند که در نهایت به کشور شما ختم می‌شود. هم‌چنین هر خط هوایی بین دو کشور مشخص می‌کند که این مسافت باید در چند ساعت طی شود و هر هواپیمایی که از آن خط استفاده می‌کند باید حرکت بین آن دو کشور را طوری انجام دهد که زمان آن برابر با مقدار تعیین شده باشد.
پس از مشخص شدن زمان مذاکرات، آقای رئیس‌جمهور به شما خبر می‌دهد که باید مذاکرات $k$ ساعت به تعویق بیافتد. از آنجایی که شما دوست ندارید برنامه مذاکرات را تغییر دهید، تنها راه برای رسیدن به مقصود رئیس‌جمهور این است که کاری انجام دهید که سفر هیئت حداقل $k$ ساعت بیشتر به طول انجامد. شما نمی‌دانید که این سفر با استفاده از چه مسیری انجام می‌شود ولی مطمئن هستنید که این مسیر مسیری است که طول آن کمینه است. شما می‌توانید با دادن مقدار مشخصی پول به رئیس یک خط هوایی زمان مشخص شده برای سفر بین دو کشور مربوط به آن خط را یک ساعت افزایش دهید. به صورت دقیق‌تر برای این که زمان سفر یک خط هوایی را $a$ واحد افزایش دهید باید $a$ برابر مقدار مشخص شده به رئیس آن خط پول دهید. دقت کنید که پس از دادن پول به رئیس‌های خطوط هوایی و تغییر زمان سفر خطوط، هیئت نمایندگان از زمان جدید خطوط با خبر می‌شوند و سفر خود را طوری مشخص می‌کنند که طول سفر آن‌ها در سیستم جدید کمینه باشد. شما می‌خواهید طوری زمان تعیین شده برای خطوط را افزایش دهید که زمان سفر هیئت به کشور شما حداقل $k$ ساعت (نسبت به زمان قبلی) افزایش پیدا کند. شما باید برنامه‌ای بنویسید که با دریافت اطلاعات مربوط به کشورها و خطوط هوایی بین آن‌ها با خرج کمترین هزینه این کار را انجام دهد.
در تنها سطر خروجی کمترین پول لازم برای رسیدن به هدف را چاپ نمایید.\\
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 3 1 2 1 3 2 3 1 4 1 3 3 5 | 19 |