# 终点和起点

预估时间限制：1.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

运输网络中有若干可出发站和若干可接收站。只需选择一个出发站和一个接收站完成运输，求最小的总路程。

(本故事由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

### 输入

```text
5 5
0 2 1 0 1
1 2 5
2 3 2
4 2 1
4 5 9
1 5 20
```

### 输出

```text
3
```

### 样例 2

### 输入

```text
3 2
0 2 1
1 2 0
1 1 5
```

### 输出

```text
-1
```

### 样例 3

### 输入

```text
2 1
0 1
1 2 0
```

### 输出

```text
0
```

## 样例解释

第一组选择起点 $4$ 和终点 $3$ ，经过 $4\to2\to3$ ，总权值为 $1+2=3$ .第二组无法到达终点 $3$ .第三组的起终点之间有零权边，答案为零。

![第一组样例的网络，标注起终点集合](assets/network.svg)

节点中的 $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% | 无额外条件 |