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