Dijkstra Finds the Shortest Path I

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

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 a length of 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 ≤ 500
1 ≤ m ≤ 10⁵
Edge lengths in the graph do not exceed 10000.

Input Sample:

3 3
1 2 2
2 3 1
1 3 4

Output Sample:

3