{"raw_statement":[{"iden":"problem statement","content":"We have $N$ points numbered $1$ to $N$ arranged in a line in this order.\nTakahashi 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:\n\n*   The operation uses integers $L_i$ and $R_i$ between $1$ and $N$ (inclusive), and a positive integer $C_i$. For every pair of integers $(s, t)$ such that $L_i \\leq s < t \\leq R_i$, add an edge of length $C_i$ between Vertex $s$ and Vertex $t$.\n\nThe integers $L_1, ..., L_M$, $R_1, ..., R_M$, $C_1, ..., C_M$ are all given as input.\nTakahashi 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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq L_i < R_i \\leq N$\n*   $1 \\leq C_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$L_1$ $R_1$ $C_1$\n$:$\n$L_M$ $R_M$ $C_M$"},{"iden":"sample input 1","content":"4 3\n1 3 2\n2 4 3\n1 4 6"},{"iden":"sample output 1","content":"5\n\nWe 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$."},{"iden":"sample input 2","content":"4 2\n1 2 1\n3 4 2"},{"iden":"sample output 2","content":"\\-1"},{"iden":"sample input 3","content":"10 7\n1 5 18\n3 4 8\n1 3 5\n4 7 10\n5 9 8\n6 10 5\n8 10 3"},{"iden":"sample output 3","content":"28"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}