题目描述

给定一个由 $N$ 个顶点组成的图。每个顶点都有一个编号 $1,\\ 2,\\ ...,\\ N$。第 $i$ ($1\\leq i\\leq N$) 个顶点具有非负整数权重 $a_i$。

初始时，图中没有边。你可以向图中添加无向边。候选边共有 $M$ 条。边的编号为 $1,\\ 2,\\ ...,\\ M$。第 $i$ ($1\\leq i\\leq M$) 条边的端点为顶点 $x_i$ 和 $y_i$，并且具有非负整数权重 $z_i$。

你的目标是将所有顶点连接起来。为此，你可以任意次选择一条尚未添加到图中的边并将其添加到图中。但是，必须始终满足以下条件：

• 对于图中的任何连通分量，$(顶点权重总和)\\geq(边权重总和)$。

判断是否可以将所有顶点连接起来。如果可以，输出一种方法来添加边到图中。

约束条件

• $2\\leq N\\leq10^5$
• $a_i$ 是整数，$0\\leq a_i\\leq10^9$
• $1\\leq M\\leq10^5$
• $1\\leq x_i<y_i\\leq N$
• $z_i$ 是整数，$0\\leq z_i\\leq10^9$

输入格式

输入是从标准输入读取的以下格式。

$N$ $M$ $a_1$ $a_2$ $...$ $a_N$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ $:$ $x_M$ $y_M$ $z_M$

输出格式

如果无法将所有顶点连接起来，则只输出 -1。

如果可以将所有顶点连接起来，则按照以下方式输出添加边到图中的方法。

• 第一行输出添加到图中的边的数量 $m$ ($1\\leq m\\leq M$)。
• 接下来的 $m$ 行中，第 $k$ 行输出要添加的第 $k$ 条边的编号 $i_k$ ($1\\leq i_k\\leq M$)。

示例 1

4 3
50 0 0 50
1 2 0
2 3 100
3 4 0

示例 1 输出

3
1
3
2

必须最后添加第 $2$ 条边。

示例 2

2 3
50 50
1 2 100
1 2 101
1 2 102

示例 2 输出

1
1

包含重复边。

示例 3

3 1
50 50 50
1 2 100

示例 3 输出

-1

无法将所有顶点连接起来。