终点和起点¶
预估时间限制：1.5 秒。内存限制：128 MB。
实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
运输网络中有若干可出发站和若干可接收站。只需选择一个出发站和一个接收站完成运输，求最小的总路程。
(本故事由GPT-6重写)
形式化问题描述¶
给定一个有 \(n\) 个点、\(m\) 条非负权无向边的图，点编号为 \(1,\ldots,n\) .标记 \(b_i\) 定义两个不相交集合：\(b_i=0\) 时点 \(i\) 属于起点集合 \(S\) ；\(b_i=1\) 时属于终点集合 \(T\) ；\(b_i=2\) 时两者均不属于。
可以从 \(S\) 中任意选择一个起点，从 \(T\) 中任意选择一个终点。求所有这样的路径中，边权之和的最小值。若不存在路径，包括任一集合为空的情况，输出 \(-1\) .允许重边、自环和零权边。
输入格式¶
第一行两个整数 \(n,m\) .第二行 \(n\) 个整数 \(b_1,\ldots,b_n\) .接下来 \(m\) 行，每行三个整数 \(u,v,c\) ，表示点 \(u\) 与点 \(v\) 之间有一条权值为 \(c\) 的无向边。
输出格式¶
输出一行一个整数：最小路径权值；若不存在符合条件的路径，输出 \(-1\) .
样例¶
样例 1¶
输入¶
5 5
0 2 1 0 1
1 2 5
2 3 2
4 2 1
4 5 9
1 5 20
输出¶
3
样例 2¶
输入¶
3 2
0 2 1
1 2 0
1 1 5
输出¶
-1
样例 3¶
输入¶
2 1
0 1
1 2 0
输出¶
0
样例解释¶
第一组选择起点 \(4\) 和终点 \(3\) ，经过 \(4\to2\to3\) ，总权值为 \(1+2=3\) .第二组无法到达终点 \(3\) .第三组的起终点之间有零权边，答案为零。
节点中的 \(S,T\) 表示集合成员，边上的数字是权值。强调的两条边给出最优路径。
数据范围与保证¶
对所有数据，\(1\le n,m\le5\times10^5\) ，\(b_i\in\{0,1,2\}\) ，\(1\le u,v\le n\) ，\(0\le c\le10^9\) .集合可以为空；图不保证连通。
| 分值比例 | 额外条件 |
|---|---|
| 40% | \(n\le500\) ，且 \(\lvert S\rvert,\lvert T\rvert\le1\) |
| 20% | \(\lvert S\rvert,\lvert T\rvert\le1\) |
| 40% | 无额外条件 |