{"problem":{"name":"Shortest Path on a Line","description":{"content":"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. Tak","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"nikkei2019_2_qual_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"nikkei2019_2_qual_d","tags":[],"sample_group":[["4 3\n1 3 2\n2 4 3\n1 4 6","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$."],["4 2\n1 2 1\n3 4 2","\\-1"],["10 7\n1 5 18\n3 4 8\n1 3 5\n4 7 10\n5 9 8\n6 10 5\n8 10 3","28"]],"created_at":"2026-03-03 11:01:13"}}