Score : 600 points
We have N points numbered 1 to N arranged in a line in this order.
Takahashi decides to make an undirected graph, using these points as the vertices. In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph. The i-th operation is as follows:
The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.
Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.
Input is given from Standard Input in the following format:
N M L_1 R_1 C_1 : L_M R_M C_M
Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1
instead.
4 3 1 3 2 2 4 3 1 4 6
5
We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.
4 2 1 2 1 3 4 2
-1
10 7 1 5 18 3 4 8 1 3 5 4 7 10 5 9 8 6 10 5 8 10 3
28