题目描述

题目译自 European Girls' Olympiad in Informatics 2021 Day2 T3. Angry Cows

近年来，极端绿色牛病（EGOI）迅速传播，这种疾病让牛对徒步者变得危险。在多次事故后，人们决定将牛群放牧区域与阿尔卑斯山脉中徒步者活动的区域分隔开来。

你得到了一份阿尔卑斯山的地图。地图上有 $n$ 个区域，每个区域可能是牛群区域、徒步区域或未使用区域。某些区域对之间通过双向小径连接，每条小径有一个非负长度。（用图论术语来说，地图是一个带权边的无向图。）

你可以在某些区域修建围墙。一旦在某个区域修建了围墙，该区域对徒步者和牛群都变得不可通行——他们将无法通过这个区域。

你的任务是选择一组修建围墙的区域，这组区域必须满足以下条件：

• 只能包含未使用区域。
• 必须将牛群区域与徒步区域分隔开。也就是说，牛无法通过小径从牛群区域走到徒步区域（除非通过有围墙的区域）。
• 不能将任意两个徒步区域分隔开。也就是说，徒步者仍能通过小径从任一徒步区域走到另一徒步区域（不通过有围墙的区域）。

如果有多种方法可以实现上述目标，我们需要考虑围墙维护的便捷性。围墙将由专门的维护团队负责，每个徒步区域都有一个这样的团队。

对于任意区域 $A$，我们定义其偏远度为从 $A$ 到某个徒步区域的最短小径长度。（路径长度是其包含的所有小径长度的总和。注意，这些路径可能经过围墙或牛群区域——维护团队拥有通过这些区域所需的所有技能和设备。）

一组区域的偏远度是该组中任一区域的最大偏远度。

在所有满足要求的围墙区域集合中，找出并返回一个偏远度最小的集合。如果有多个这样的集合，你可以返回任意一个。

注意，区域数量并不重要。特别地，不要求使用尽可能少的围墙。

输入格式

第一行包含两个用空格分隔的整数 $n,m$ ($2 \leq n \leq 3 \cdot 10^5$, $n-1 \leq m \leq 3 \cdot 10^5$)，分别表示区域数量和小径数量。区域编号从 $1$ 到 $n$。

第二行包含 $n$ 个用空格分隔的整数 $t_1, \ldots, t_n$，其中 $t_i$ 为 $-1$ 表示第 $i$ 个区域是牛群区域，为 $0$ 表示未使用区域，为 $1$ 表示徒步区域。

接下来的 $m$ 行描述小径。第 $j$ 行包含三个用空格分隔的整数 $a_j, b_j, \ell_j$ ($1 \leq a_j < b_j \leq n$, $0 \leq \ell_j \leq 10^9$)，表示区域 $a_j$ 和 $b_j$ 之间有一条长度为 $\ell_j$ 的小径。

保证：

• 任意两个区域之间最多有一条小径。
• 当前可以通过零条或多条小径在任意两个区域之间通行。
• 至少有一个牛群区域。
• 至少有一个徒步区域。

输出格式

如果无法按要求修建围墙，输出 $-1$。

否则，第一行输出一个整数 $k$，表示你想要修建的围墙数量。第二行输出 $k$ 个整数，表示你想要修建围墙的区域编号。（这些编号必须是 $1$ 到 $n$ 之间的不同整数，顺序不限。）

你可以输出任意一个合法的且具有最小偏远度的围墙集合。

样例 1

输入

10 14
1 0 1 0 0 0 0 0 -1 -1
1 2 1
1 6 1
2 3 1
2 5 2
3 4 1
4 5 1
4 8 2
5 6 1
5 7 1
6 7 2
6 10 1
7 8 1
7 9 1
8 9 1

输出

3
4 5 6

在所有图示中，徒步区域用蓝色（虚线）表示，牛群区域用棕色（实线）表示，围墙用橙色（虚线）表示。

最小可能的偏远度是 $2$，通过在区域 $3, 4, 5$ 和 $6$ 中修建围墙实现。注意，不能在区域 $4, 2, 6$ 中修建围墙，尽管这会使偏远度为 $1$，因为那样会导致徒步区域 $1$ 和 $3$ 之间无法通行（除非通过围墙）。

样例 2

输入

5 5
1 0 0 -1 0
1 2 1000
2 3 1000
3 4 10
4 5 10
1 5 10

输出

2
3 5

区域 $2$ 的偏远度是 $1000$，区域 $3$ 的偏远度是 $30$，因为可以通过路径 $1-5-4-3$ 到达。（提醒：维护团队可以穿过围墙和牛群区域。）因此，我们应在区域 $3$ 和 $5$（而不是 $2$）修建围墙，偏远度为 $30$。

样例 3

输入

4 3
1 0 -1 1
1 2 0
2 3 21
2 4 13

输出

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	$7$	$n \leq 10$
2	$22$	所有 $\ell_j = 0$
3	$16$	恰好有一个徒步区域
4	$11$	恰好有 $n-1$ 条小径（用图论术语，图是一棵树）
5	$8$	$n, m \leq 2000$ 且所有 $\ell_j = 1$
6	$36$	无附加限制