Dijkstra Finds the Shortest Path ||

Submit solution
Points: 1
Time limit: 2.0s
Memory limit: 256M
Problem type
Allowed languages
Python

Given a directed graph with n nodes and m edges, which may contain duplicate edges and self-loops, all edge weights are non-negative.

Please find the shortest distance from node 1 to node n. If it is impossible to reach node n from node 1, output -1.

Input Format
The first line contains integers n and m.

The next m lines each contain three integers x, y, z, indicating there is a directed edge from node x to node y with length z.

Output Format
Output an integer, representing the shortest distance from node 1 to node n.

If no path exists, output -1.

Data Range
1 ≤ n, m ≤ 1.5 × 105,
All edge weights in the graph are at least 0 and at most 10000.
It is guaranteed that if the shortest path exists, its length does not exceed 109.

Input Sample:

3 3
1 2 2
2 3 1
1 3 4

Output Sample:

3

Comments