近年来，一种被称为“极端绿色牛病”（Extremely Green Oxen Illness，简称 EGOI）的疾病迅速蔓延，这种疾病使得牛对徒步旅行者具有危险性。在发生多起事故后，我们决定将牛群放牧的区域与阿尔卑斯山中人们想要徒步旅行的区域隔离开来。

你将获得一张阿尔卑斯山的地图。地图上有 $n$ 个区域。每个区域要么是牛群聚集区，要么是徒步旅行区，要么是未使用区域。一些区域对之间由双向路径连接。每条路径都有一个非负长度。（用图论术语来说，这张地图是一个带权无向图。）

你可以在某些区域建造围墙。一旦你在某个区域建造了围墙，该区域对徒步旅行者和牛群来说就变得不可通行——它们将无法再穿过这样的区域。

你的任务是选择一组要放置围墙的区域。这组区域必须满足以下条件：

• 它必须仅由未使用区域组成。
• 它必须将牛群聚集区与徒步旅行区隔离开来。也就是说，牛群不应再能够沿着路径从牛群聚集区走到徒步旅行区（且不经过带有围墙的区域）。
• 它不得将任何徒步旅行区彼此隔离开来。也就是说，徒步旅行者仍然应该能够沿着路径从任何一个徒步旅行区走到任何其他徒步旅行区（且不经过带有围墙的区域）。

如果存在多种达到上述目标的方法，我们将关注围墙的维护便利性。围墙由专门的团队维护。每个徒步旅行区都有一个这样的团队。

对于任何区域 $A$，我们将其“偏远度”（remoteness）定义为从 $A$ 到某个徒步旅行区的路径的最小长度。（路径长度是其路径上各条路径长度之和。注意，这些路径可以穿过围墙和牛群聚集区——围墙维护团队拥有完成此操作所需的所有技能和设备。）

一组围墙区域的“偏远度”定义为该集合中任何区域的最大偏远度。

在所有具有所需属性的围墙区域集合中，找到并返回一个具有尽可能小的偏远度的集合。如果存在多个这样的集合，你可以返回其中任何一个。

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

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$n - 1 \le m \le 3 \cdot 10^5$）——分别是区域和路径的数量。区域编号从 $1$ 到 $n$。

第二行包含 $n$ 个空格分隔的整数 $t_1, \dots, t_n$，其中如果第 $i$ 个区域是牛群聚集区，则 $t_i$ 为 $-1$；如果是未使用区域，则为 $0$；如果是徒步旅行区，则为 $1$。

接下来的 $m$ 行描述路径。第 $j$ 行包含三个空格分隔的整数 $a_j, b_j$ 和 $\ell_j$（$1 \le a_j < b_j \le n$，$0 \le \ell_j \le 10^9$），表示区域 $a_j$ 和 $b_j$ 之间长度为 $\ell_j$ 的路径。

保证： 任意两个区域之间最多只有一条路径。 目前可以通过零条或多条路径在任意两个区域之间行走。 至少有一个牛群聚集区。 至少有一个徒步旅行区。

输出格式

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

否则，第一行应包含一个整数 $k$——你想要建造的围墙数量。第二行应包含 $k$ 个整数——你想要建造围墙的区域编号。（这些数字必须是 $1$ 到 $n$ 之间互不相同的数字。它们不需要按任何特定顺序排列。）

如果输出是一组允许的且具有最小偏远度的围墙，则该输出将被接受。

子任务

• 子任务 1（7 分）：$n \le 10$。
• 子任务 2（22 分）：所有长度 $\ell_j = 0$。
• 子任务 3（16 分）：恰好有一个徒步旅行区。
• 子任务 4（11 分）：恰好有 $n - 1$ 条路径（用图论术语来说，该图是一棵树）。
• 子任务 5（8 分）：$n, m \le 2000$ 且所有长度 $\ell_j = 1$。
• 子任务 6（36 分）：没有额外限制。

样例

样例输入 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

样例输出 1

3
4 5 6

样例输入 2

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

样例输出 2

2
3 5

样例输入 3

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

样例输出 3

-1

说明

在所有图中，蓝色（虚线）用于徒步旅行区，棕色（实心）用于牛群聚集区，橙色（虚线）用于围墙。

在第一个样例中，最小可能的偏远度为 2，通过在区域 4、5 和 6 放置围墙实现。注意，不能在区域 4、2 和 6 放置围墙，尽管这会产生 1 的偏远度，因为那样将无法在不经过围墙的情况下在徒步旅行区 1 和 3 之间通行。

在第二个样例中，区域 2 的偏远度为 1000，区域 3 的偏远度为 30，因为它可以通过路径 1–5–4–3 到达。（回想一下，维护团队可以穿过围墙和牛群聚集区。）因此，我们应该在区域 5 和 3（而不是 2）放置围墙，偏远度将为 30。