AT_pakencamp_2021_day2_l ジグザグ道

给定一个拥有 $N$ 个顶点和 $M$ 条边的简单连通无向图。顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。每条边 $i$ 连接着顶点 $U_i$ 和 $V_i$，且其权重为 $W_i$。所有边的权重都互不相同。 现在，找一条从顶点 $1$ 到顶点 $N$ 的路径。路径中边的权重按顺序形成序列 $C = (C_1, C_2, \ldots, C_k)$。如果这条路径满足以下一种条件，则称其为“锯齿路径”： - 权重依次升降交错，即 $C_1 < C_2 > C_3 < \cdots$ 或 $C_1 > C_2 < C_3 > \cdots$。具体是： - 对于任意整数 $i$，当 $1 \leq i \leq k - 1$ 且 $i$ 为奇数时，有 $C_i < C_{i+1}$；当 $i$ 为偶数时，有 $C_i > C_{i+1}$。 - 对于任意整数 $i$，当 $1 \leq i \leq k - 1$ 且 $i$ 为奇数时，有 $C_i > C_{i+1}$；当 $i$ 为偶数时，有 $C_i < C_{i+1}$。 请判断这样的“锯齿路径”是否存在？如果存在，求出边权重之和的最小值。

输入从标准输入以以下形式给出： > $N$ $M$ $U_1$ $V_1$ $W_1$ $U_2$ $V_2$ $W_2$ $\cdots$ $U_M$ $V_M$ $W_M$

如果存在满足条件的“锯齿路径”，则输出其边权重和的最小值。如果不存在这样的路径，则输出 `-1`。

- $2 \leq N \leq 10^5$ - $N - 1 \leq M \leq \min \left( \frac{N(N-1)}{2}, 10^5 \right)$ - $1 \leq U_i < V_i \leq N$ - $1 \leq W_i \leq 10^9$ - 不存在相同的边，即 $(U_i, V_i) \neq (U_j, V_j)$ 其中 $i \neq j$ - 权重不同，即 $W_i \neq W_j$ 其中 $i \neq j$ - 图是简单且连通的 - 输入的所有值均为整数 ### 样例解释 例如，按顺序通过边 $1, 5, 3, 4$，可以得到 $C = (4, 3, 6, 1)$，满足“锯齿路径”的条件，权重和为 $14$。但按 $1, 5, 2$ 顺序经过的路径，得 $C = (4, 3, 2)$，则不满足条件。 **本翻译由 AI 自动生成**