T363959 2023省熟中集训#1 F 规划

hyy 生活在一个没有道路的国家，而他刚被钦定为城市道路规划员。

在 $H$ 国有 $n$ 座城市，初始没有道路相连。 hyy 将做 $m$ 次规划，第 $i$ 次规划将在编号在 $[L_i, R_i]$ 间的任意两座城市之间修建一条 $W_i$ 长度的道路。 漫长的时间过后，所有道路都修好了，请你回答现在从 $1$ 号城市到 $n$ 号城市最少需要走多远才能到达。

第一行包含两个整数 $n$ 和 $m$。 接下来的 $m$ 行，每行包括三个整数 $L_i$, $R_i$ 和 $W_i$, 其中 $1 \leq L_i \leq R_i \leq n, 1 \leq W_i \leq 10^9$。

输出一个整数。 如果不可能到达 $n$ 号城市，输出 $-1$，否则输出最短距离。

对于 20% 的数据，$1 \leq n,m \leq 100$； 对于 50% 的数据，$1 \leq n,m \leq 500$； 对于 80% 的数据，$1 \leq n,m \leq 5 \times 10^4$； 对于 100% 的数据，$1 \leq n,m \leq 3 \times 10^5$ 。