← 返回题目列表

AtCoder · icpc2015summer_day2_j

J. 串联

中文机器翻译题面 查看原题

问题陈述

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

即使将所有边添加到图中后,也无法连接所有顶点。