题目描述

哥萨克·乌斯终于找到了自己梦想中的国家。这个国家有 $n$ 座城市，城市之间一开始没有任何道路。乌斯想改变这种情况，于是设计了 $m$ 条可以修建的无向道路。每条道路连接两座不同的城市。

问题在于：每座城市 $i$ 最多能拿出 $c_i$ 个硬币用于修路，而第 $j$ 条道路的修建费用为 $w_j$ 个硬币。因此，乌斯决定只修建若干条道路，只要最终所有城市连通即可。

在规划时，乌斯意识到：随着道路逐条修建，城市会合并成若干连通块。若要修建第 $j$ 条道路，则这条道路两端所在连通块的总预算必须至少为 $w_j$，因为必须先支付费用，之后道路才能建成。道路建成后，两个连通块的预算合并，并扣除这条道路的费用。

已知每座城市的预算 $c_i$，以及每条候选道路的两个端点 $v_i,u_i$ 和费用 $w_i$。请判断是否可以选择若干条道路并安排修建顺序，使得最后所有城市连通；如果可以，请输出一种修建顺序。

函数提交说明

原题提供如下函数用于报告要修建的道路：

void add(int i);

调用该函数表示修建编号为 $i$ 的道路。

你需要实现：

bool solve(int n, int m, int g,
           vector<int> c,
           vector<int> v,
           vector<int> u,
           vector<int> w);

参数含义如下：

• $n$：城市数；
• $m$：候选道路数；
• $g$：测试块编号；
• $c_i$：第 $i$ 座城市的初始预算；
• $v_i,u_i$：第 $i$ 条道路连接的两个城市；
• $w_i$：修建第 $i$ 条道路需要的硬币数。

该函数应在可行时返回 true，不可行时返回 false。若返回 true，则在返回前必须按照实际修建顺序调用 add 输出所有修建道路。

输入格式

第一行包含三个整数 $n,m,g$（$1\le n\le10^6$，$0\le m\le10^6$，$0\le g\le7$），分别表示城市数、道路数和测试块编号。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\le c_i\le10^6$），表示每座城市的初始预算。

接下来 $m$ 行，每行包含三个整数 $v_i,u_i,w_i$（$1\le v_i,u_i\le n$，$1\le w_i\le10^6$），表示第 $i$ 条道路的端点和修建费用。

输出格式

若不可行，第一行输出 -1。

否则第一行输出 $q$，表示修建道路条数；随后 $q$ 行每行输出一个整数 $x$，表示修建的道路编号。

样例 1

4 5 0
2 5 2 4
1 2 7
3 4 4
1 4 5
4 2 3
3 2 4

3
4
2
3

样例 2

3 3 0
6 2 5
2 3 9
2 1 5
1 3 10

-1

样例说明

样例一中，先修建编号为 $4$ 的道路，城市 $2$ 与 $4$ 合并，并从其总预算中支付 $3$ 个硬币，合并块剩余 $6$ 个硬币。再修建编号为 $2$ 的道路后，该连通块预算变为 $4$。最后修建第 $3$ 条道路，所有城市连通且预算足够支付费用。

样例二中，不存在一种道路选择和修建顺序能够让所有城市连通且支付所有费用。

计分方式