सबसे छोटा रास्ता खोजें 2
आपके पास एक नक्शा है जिसमें
n शहर हैं और उन्हें जोड़ने वाली m द्विदिश सड़कें (bidirectional roads) हैं। प्रत्येक सड़क की गैर-नकारात्मक पूर्णांक लंबाई होती है, जिसे से दर्शाया गया है। आपका कार्य शहर 1 से शहर n तक जाने वाले सबसे छोटे रास्ते की लंबाई खोजना है।इनपुट
पहली पंक्ति में दो स्पेस से अलग किए गए पूर्णांक
n और m होते हैं (), जो क्रमशः शहरों की संख्या और सड़कों की संख्या को दर्शाते हैं।अगली
m पंक्तियों में, प्रत्येक में तीन स्पेस से अलग किए गए पूर्णांक , , और होते हैं, जो शहर और शहर के बीच की सड़क का प्रतिनिधित्व करते हैं; इस सड़क की लंबाई होती है ()।आउटपुट
एक संपूर्ण संख्या (integer), जो शहर
1 से शहर n तक जाने वाले सबसे छोटे रास्ते की लंबाई को दर्शाती है।उदाहरण
इनपुट | आउटपुट |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB