ज्ञान की भूलभुलैया
Problem
आकर्षण "ज्ञान की भूलभुलैया" समर कंप्यूटर स्कूल (LCS) में बनाया गया था। भूलभुलैया में एन कमरे होते हैं, जिनकी संख्या 1 से एन तक होती है, जिनमें से कुछ के बीच दरवाजे होते हैं। जब कोई व्यक्ति किसी द्वार से गुजरता है तो उसके ज्ञान का सूचक इस द्वार के लिए निर्धारित एक निश्चित राशि से बदल जाता है। भूलभुलैया का प्रवेश कक्ष 1 में है, बाहर निकलने के लिए – कमरा एन में। प्रत्येक छात्र एक बार भूलभुलैया से गुजरता है और प्राप्त ज्ञान की मात्रा के आधार पर एक या दूसरे अध्ययन समूह में जाता है (भूलभुलैया में प्रवेश करते समय, यह सूचक शून्य है)। आपका काम सबसे अच्छा परिणाम दिखाना है।
इनपुट:
इनपुट की पहली पंक्ति में पूर्णांक N (1 <= N <= 2000) – कमरों की संख्या और M (1 <= M <= 10000) – दरवाजों की संख्या। अगली M पंक्तियों में से प्रत्येक में द्वार का विवरण होता है - उन कमरों की संख्या जहां से यह जाता है और जिससे यह जाता है (आप केवल एक दिशा में दरवाजे से चल सकते हैं), साथ ही एक पूर्णांक जो दरवाजे से गुजरते समय ज्ञान की मात्रा में जोड़ा जाता है (यह संख्या नहीं होती है) मॉड्यूलो में 10000 से अधिक)। दरवाजे एक कमरे से खुद की ओर जा सकते हैं, दो कमरों के बीच एक से अधिक दरवाजे हो सकते हैं।
आउटपुट:
डिस्प्ले ":)" - यदि आप असीमित मात्रा में ज्ञान प्राप्त कर सकते हैं, ":(" – यदि भूलभुलैया को पार नहीं किया जा सकता है, और ज्ञान की अधिकतम मात्रा अन्यथा प्राप्त की जा सकती है।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
2 2
1 2 3
1 2 7
7 |