问题陈述
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 。
您的目标是使所有顶点连接。为此,我们需要仅添加尚未添加到图中的边。 1 您可以选择一本书并将其添加到图表中任意次。然而,以下条件在任何时候都必须成立。
- 对于图中的任何连通分量,(頂点の重みの総和)\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 。
如果所有顶点都可以连接,则输出一种向图添加边的方法,如下所示。
- 1 线表示要添加到图形中的边数。 输出 m (1\leq m\leq M)
- 2 从线 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
即使将所有边添加到图中后,也无法连接所有顶点。