给出一张无向连通图$G=(V,E)$，这个图满足：

• 对于任何一个点$x$，不存在两个不同的简单环$C_1,C_2$，使得$x$同时在这两个环上。
• 每个点和每条边都有一个$[-10^9,10^9]\cap\mathbb{Z}$内的权值。点$i$有点权$A_i$，边$(a,b)$有边权$B_{a,b}$。

定义$\mathfrak{S}$为所有连通点集$S$的全集，从小到大输出$\mathfrak{S}$中前$k$小的$W(S)$。其中$W(S)=\sum_{x\in S}A_x+\sum_{(a,b)\in E,a\in S,b\in S}{B_{a,b}}$。

输入格式

第一行包含三个正整数$n,m,k$，其中$k$意义见上文，$n,m$分别表示$|V|,|E|$（即点数和边数）。规定图中的节点用$1$到$n$的整数表示。

第二行包含$n$个整数，按次序表示点权$A_i$。

接下来$m$行，每行三个整数$a,b,B_{a,b}$，表示一条边$(a,b)$边权为$B_{a,b}$。

输出格式

先输出$\min(|\mathfrak{S}|,k)$行，每行包含一个整数，表示前$\min(|\mathfrak{S}|,k)$个$W(S)$；

如果$|\mathfrak{S}|< k$，再输出一行一个整数$-1$。

样例输入

6 5 1926
32 64 128 256 512 1024
1 2 1
2 3 2
3 4 4
4 5 8
5 6 16

样例输出

32
64
97
128
194
227
256
388
454
487
512
776
908
974
1007
1024
1552
1816
1948
2014
2047
-1

样例解释

选择的前四个点集分别为：$\{1\},\{2\},\{1,2\},\{3\}$。

数据范围

保证答案所有数的绝对值$\leq 10^{18}$；共$20$个测试点，每个测试点均为$5$分；保证图中没有重边或环；保证所有$A_i,B_{a,b}\in [L=-10^9,R=10^9]\cap\mathbb{Z}$；时间限制为$1s$，空间限制为$666MB$。

对于$100\%$的数据，满足$n,m,k\leq 2^{17}$。

留空表示与$100\%$数据的限制相同。