Problem
برای مدرسه کامپیوتر تابستانی بعدی، تصمیم گرفته شد که هم برای دانش آموزان مدرسه و هم برای همه معلمان حلقه هایی آماده شود.
طراح که عادت داشت کارهای مهم را در آخرین لحظه انجام دهد، دو روز قبل از شروع مدرسه طرح را تمام کرد. یک روز دیگر طول می کشد تا سازنده لیوان ها را بسازد و تصویری روی آنها بگذارد. تنها 24 ساعت طول می کشد تا ناتو لیوان ها را از کارخانه به LKSH ببرد.
سفارش 10,000,000 لیوان (یعنی این همان مقداری است که سازمان دهندگان سفارش داده اند) البته با یک پرواز قابل برداشت نیست. با این حال، برای اولین پرواز می خواهم حداکثر تعداد لیوان را بیاورم. یک کامیون سنگین برای حمل و نقل سفارش داده شد. اما یک اخطار وجود دارد: در برخی جاده ها وزن خودرو محدودیت دارد. بنابراین، اگر ماشین با لیوان تا کره چشم بارگیری شود، ممکن است نتوان از کوتاه ترین مسیر استفاده کرد، اما مجبور به انحراف خواهید بود. حتی ممکن است این اتفاق بیفتد که به این دلیل کامیون وقت نداشته باشد که به موقع به کمپ برسد و نمی توان این اجازه را داد. بنابراین، چند لیوان را می توان در ماشین بار کرد تا وقت داشته باشیم که این محموله ارزشمند را به موقع و بدون نقض قوانین جاده ای بیاوریم؟
ورودی
خط اول شامل اعداد n (1≤n≤500) و m است - تعداد گره‌ها در نقشه راه و تعداد جاده‌ها، به ترتیب. خطوط متر بعدی حاوی اطلاعاتی در مورد جاده ها هستند. هر جاده در یک خط جداگانه به شرح زیر توضیح داده شده است. ابتدا اعداد نقاط تقاطعی که توسط این جاده به هم متصل می شوند، سپس مدت زمان حرکت در این جاده و در نهایت حداکثر وزن خودرویی که مجاز به تردد در این جاده است، آورده شده است. مشخص است که همه جاده ها نقاط مختلفی را به هم متصل می کنند و برای هر جفت نقطه حداکثر یک جاده وجود دارد که مستقیماً آنها را به هم وصل می کند. همه اعداد با یک یا چند فاصله از هم جدا می شوند.
نقاط گرهی از 1 تا n شماره گذاری می شوند. در همان زمان، کارخانه تولید لیوان دارای شماره 1 و LKSH - شماره n است. زمان سفر در جاده به دقیقه داده می شود و از 1440 (24 ساعت) تجاوز نمی کند. حد جرم بر حسب گرم است و از یک میلیارد تجاوز نمی کند. علاوه بر این، مشخص است که یک لیوان 100 گرم وزن دارد و یک کامیون خالی - 3 تن.
خروجی
چاپ یک عدد - حداکثر تعداد لیوان هایی که می توان در اولین پرواز با خود آورد و بیش از 24 ساعت صرف نمی شود.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
3 3
3000220 1 2 10
2 3 20 3000201
1 3 1 3000099
|
2 |