सबसे छोटा रास्ता खोजें 3
आपको
n शहरों और m द्विदिश (bidirectional) सड़कों से बने एक नक्शे की जानकारी दी गई है। हर सड़क की लंबाई एक गैर-ऋणात्मक पूर्णांक (non-negative integer) होती है, जिसका मान के रूप में दिया गया है। आपका कार्य शहर 1 से शहर n तक के सबसे छोटे रास्ते की लंबाई खोजने का है।इनपुट (Input)
पहली पंक्ति में दो रिक्त-सेparated पूर्णांक
n और m ($2 \le n \le 10^5, 1 \le m \le 10^5$) होते हैं, जो क्रमशः शहरों की संख्या और सड़कों की संख्या का संकेत देते हैं।अगली
m पंक्तियों में से प्रत्येक में तीन रिक्त-सेparated पूर्णांक u_i, v_i, और w_i दिए होते हैं। ये तीनों मान बताते हैं कि शहर u_i और शहर v_i के बीच एक सड़क है, जिसकी लंबाई w_i है ($1 \le ui, vi \le n, \, 1 \le w_i \le 10^9$)।आउटपुट (Output)
एकल पूर्णांक जो शहर
1 से शहर n तक के सबसे छोटे रास्ते की लंबाई दर्शाता है।उदाहरण (Examples)
Input | Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB