Problem
अगले ग्रीष्मकालीन कंप्यूटर स्कूल के लिए, स्कूली बच्चों और सभी शिक्षकों दोनों के लिए सर्कल तैयार करने का निर्णय लिया गया।
महत्त्वपूर्ण कार्य अंतिम क्षण में करने की आदत होने के कारण, डिज़ाइनर ने स्कूल शुरू होने से दो दिन पहले लेआउट तैयार कर लिया। निर्माता को मग बनाने और उन पर एक छवि लगाने में एक और दिन लगेगा। मग को कारखाने से LKSH तक ले जाने में NATO को केवल 24 घंटे लगते हैं।
10,000,000 मग का ऑर्डर (अर्थात्, आयोजकों ने इतने ही ऑर्डर दिए थे), निश्चित रूप से, एक उड़ान में नहीं लिया जा सकता है। हालाँकि, पहली उड़ान के लिए मैं अधिक से अधिक संख्या में मग लाना चाहता हूँ। परिवहन के लिए एक भारी ट्रक का आदेश दिया गया था। लेकिन एक चेतावनी है: कुछ सड़कों पर कार के वजन की सीमा होती है। इसलिए, यदि कार मग से भरी हुई है, तो सबसे छोटे मार्ग का उपयोग करना संभव नहीं हो सकता है, लेकिन आपको एक चक्कर लगाना होगा। यह भी हो सकता है कि इस वजह से ट्रक को समय पर कैंप तक पहुंचने का समय नहीं मिलेगा और इसकी अनुमति नहीं दी जा सकती। तो, इस मूल्यवान माल को समय पर लाने के लिए और सड़क के नियमों का उल्लंघन किए बिना कार में कितने मग लोड किए जा सकते हैं?
इनपुट
पहली पंक्ति में क्रमशः n (1≤n≤500) और m - रोड मैप में नोड्स की संख्या और सड़कों की संख्या होती है। अगली m पंक्तियों में सड़कों के बारे में जानकारी होती है। प्रत्येक सड़क को एक अलग पंक्ति में निम्नानुसार वर्णित किया गया है। सबसे पहले, इस सड़क से जुड़े जंक्शन बिंदुओं की संख्या दी गई है, फिर इस सड़क पर यात्रा करने में लगने वाला समय और अंत में, इस सड़क पर चलने वाली कार का अधिकतम वजन। यह ज्ञात है कि सभी सड़कें अलग-अलग बिंदुओं को जोड़ती हैं, और प्रत्येक जोड़ी बिंदुओं के लिए अधिक से अधिक एक सड़क उन्हें सीधे जोड़ती है। सभी संख्याएँ एक या अधिक रिक्तियों द्वारा अलग की जाती हैं।
नोडल बिंदु 1 से n तक गिने जाते हैं। इसी समय, मग के उत्पादन के लिए संयंत्र की संख्या 1 है, और एलकेएसएच - संख्या एन। सड़क पर यात्रा का समय मिनटों में दिया गया है और यह 1440 (24 घंटे) से अधिक नहीं है। द्रव्यमान सीमा ग्राम में दी गई है और एक अरब से अधिक नहीं है। इसके अलावा, यह ज्ञात है कि एक मग का वजन 100 ग्राम होता है, और एक खाली ट्रक - 3 टन।
आउटपुट
एक नंबर प्रिंट करें - मग की अधिकतम संख्या जिसे पहली उड़ान पर लाया जा सकता है, 24 घंटे से अधिक खर्च नहीं।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
2 |