配点 : 500 点
問題文
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} 。
之字形路径 将其定义为存在吗?如果存在,还求经过的边的权重之和的最小值。
制約
- 2 \leq N \leq 10^5
- N - 1 \leq M \leq \min \left( \cfrac{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)
- 作为输入给出的图很简单且连通 如果
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
出力
之字形路径
将其定义为存在,则经过的边的权重之和的最小值为
如果 1 行输出。之字形路径
将其定义为不存在,则 -1 该值应乘以 1 行输出。
入力例 1
5 5 1 4 4 3 5 2 2 3 6 2 5 1 3 4 3
出力例 1
14
辺 1, 5, 3, 4 的顺序通过 C = (4, 3, 6, 1) 变为 通过之字形路径 将其定义为满足条件。在这种情况下,总重量是 按照 14 。
辺 1, 5, 2 顺序遵循的路径是 C = (4, 3, 2) 旁边 不是之字形路径 将其定义为。 您将收到
入力例 2
4 3 1 2 4 2 3 6 3 4 8
出力例 2
-1
入力例 3
7 12 2 5 657831697 5 6 925940778 1 2 749029915 2 4 237755672 3 6 60634766 6 7 65418621 1 4 194639839 4 7 411656898 3 7 367905753 3 4 241675120 1 6 858592389 2 6 571202751
出力例 3
562368346
原案: primenumber_zz