【问题描述】
“凡人想以复杂的手法掩饰某件事时，往往因复杂而自掘坟墓，可是天才不会这样做。他们会选用极为单纯，但常人想象不到也绝不会选择的方法，将问题一口气复杂化。”

警察共发现了n个证据，然而其中有一些是石神伪造的。
通过证据的**两两组合**，警察可以作出一些假设，每个假设有一定价值。
现在要求你**选取其中的一部分假设**，使得**总价值**最大。
选取假设的要求是:
将**证据**看成点
将**假设**看成带权的无向边
所有的点和选取的边构成k个联通块
不允许出现环，避免作出的假设出现矛盾

我们称选取的假设**有用**，是指该假设所在的联通块中**不包含伪造的证据**。总价值等于**所有选取的有用的假设的价值乘积。**
求最大可能的总价值。

如果无法构成k个联通块则输出-1，如果能构成k个联通块但没有有用的假设则输出1。

【输入】
输入文件名为evidence.in。
第一行包含三个数n m和k，n表示证据的数量，m表示可以作出的假设数，k表示最终的联通块的数量。
第二行包含n个数fact_i，由0和1组成，如果fact_i是0则表示这个证据是伪造的，如果是1则表示这个证据是有价值的。
接下来m行每行包含三个数x_i y_i和z_i，表示第i条假设需要用到第x_i和第y_i个证据，同时这个假设的价值是z_i。

【输出】
输出文件名为evidence.out。
输出一行，包含一个整数，表示最大可能的总价值。
由于答案可能很大，所以对1000000007取模后输出。

Sample 1

Input

4 4 2
1 1 1 1
1 2 2
2 3 3
3 4 1
4 1 2

Output

6

Sample 2

Input

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

Output

12

Limitation

1s, 128MiB for each test case.
【数据说明】
对于30%的数据，m≤20
对于50%的数据，不包含伪造的证据
对于100%的数据，n≤100000，m≤200000，权值≤100