एकल छूट (Single Discount)

Alex शहर 1 में रहता है और शहर n तक पहुँचना चाहता है। वह उड़ानों का एक ऐसा मार्ग ढूँढना चाहता है जिसकी कुल कीमत सबसे कम हो, इस बात को ध्यान में रखते हुए कि उसके पास एक छूट कूपन भी है। यह छूट कूपन मार्ग के दौरान सिर्फ एक बार इस्तेमाल किया जा सकता है, जिससे किसी एक उड़ान की कीमत आधी हो जाती है। यदि किसी उड़ान की कीमत x है और वह इस पर छूट कूपन का उपयोग करता है, तो नई कीमत हो जाती है।
आपको शहर 1 से शहर n तक जाने वाले सबसे सस्ते मार्ग की कीमत निकालनी है।

इनपुट

पहली पंक्ति में दो रिक्त-सेपरेटेड पूर्णांक n और m () होते हैं, जो क्रमशः शहरों की संख्या और उड़ानों की संख्या को दर्शाते हैं।

इसके बाद की m पंक्तियाँ उड़ानों का वर्णन करती हैं। प्रत्येक पंक्ति में तीन रिक्त-सेपरेटेड पूर्णांक a, b, और () दिए गए हैं, जो शहर a से शहर b के बीच दो-तरफा उड़ान (bidirectional flight) को दर्शाते हैं, जिसकी कीमत है।

आउटपुट

केवल एक पूर्णांक प्रिंट करें, जो शहर 1 से शहर n तक के सबसे सस्ते मार्ग की कीमत को दर्शाता है।

उदाहरण