दूसरा सबसे छोटा पथ
आपको
n शहर दिए गए हैं, जिन्हें m द्विदिश सड़कों से जोड़ा गया है। प्रत्येक सड़क की लंबाई होती है। Emil, जो एक रोमांचप्रिय यात्री है, शहर 1 से शहर n तक इन सड़कों का उपयोग करके जाना चाहता है। हालांकि, उसकी योजना में एक अनोखा मोड़ है—वह उन सभी मार्गों में से सबसे छोटा मार्ग चुनेगा जो कुल सबसे छोटे मार्ग से स्पष्ट रूप से बड़े हों।दूसरे शब्दों में, आपका काम Emil की मदद करना है ताकि वह शहर
1 से शहर n तक जाने वाले दूसरे सबसे छोटे मार्ग की लंबाई का निर्धारण कर सके।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n और m दिए गए हैं, जो क्रमशः शहरों की संख्या और सड़कों की संख्या को दर्शाते हैं।
अगली m पंक्तियों में प्रत्येक में तीन पूर्णांक , , और दिए गए हैं, जो यह दर्शाते हैं कि शहर और शहर के बीच लंबाई वाली एक द्विदिश सड़क है।आउटपुट
एकमात्र पूर्णांक प्रिंट करें, जो शहर
1 से शहर n तक के दूसरे सबसे छोटे मार्ग की लंबाई व्यक्त करता है।उदाहरण
Input | Output |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB