در گراف ساده، بدون جهت و وزن‌دار $G$، رئوس، نشانگر شهرها و یال‌ها، نشان‌دهنده‌ی جاده‌های بین این شهرهایند. همچنین وزن هر یال بیانگر طول جاده متناظر است. فرض کنید برای پیمودن هر واحد طول جاده، یک لیتر بنزین مصرف می‌شود. در هر شهر یک پمپ بنزین قرار دارد. اتومبیلی داریم که باک بنزین آن $p$ لیتر گنجایش دارد و در ابتدا پر است. می‌دانیم که قیمت هر لیتر بنزین در پمپ بنزین شهر $i$ ام برابر $c_i$ است. در ضمن چون پمپ بنزینی‌ها سمج هستند، مجبوریم اگر در یک شهر بخواهیم بنزین بزنیم، باک را کاملا پر کنیم (اگر در باک مقداری بنزین مانده بود، فقط به اندازه‌ی حجم خالی باک، بنزین لازم است.) می‌خواهیم از شهر ۱ به شهر $n$ برویم به گونه‌ای که مجموع هزینه خرید بنزین کمینه شود.

در سطر اول فایل ورودی $n$ (تعداد رئوس گراف) و $p$‌ آمده است. در سطر دوم، $n$ عدد به نشانه‌ی $c_i$ ها آمده است. در سطرهای بعدی، در هر سطر سه عدد آمده است که دو عدد اول نشانگر دو انتهای یک یال و عدد سوم بیانگر طول آن یال است. در سطر آخر فایل سه عدد صفر آمده است. فرض کنید همه‌ی اعداد ورودی از نوع $Integer$ هستند و در ضمن $n\leq 100$.

در فایل خروجی کم‌ترین هزینه ممکن را بنویسید.

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