题目描述

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，图中每条边都有一个权值，代表经过这条边所耗费的时间。 你初始位于 \(1\) 号点，并且初始的“魔力值”为 \(0\)。

在图中的第 \(i\) 个点，含有一种魔力效果为 \(a_i\) 的药水。当你处于第 \(i\) 个点时，你可以选择喝下该点的药水，药水是无限多的且喝下药水不耗费任何时间。每喝下一瓶药水，你可以选择让你的魔力值增加 \(a_i\) 或者减少 \(a_i\)。在任意时刻，你的魔力值都可以是负数。

你的目标是通过在图上移动和喝药水，使得自己的魔力值恰好等于 \(V\)。请问达到目标的最少总时间是多少？如果无论如何也无法达到 \(V\) 的魔力值，请输出 -1。

输入格式

第一行包含一个正整数 \(T\) （\(1 \le T \le 10\)），表示测试数据的组数。

对于每组测试数据：

第一行包含三个正整数 \(n, m, V\) （\(1 \le n, m \le 10^4\)， \(1 \le V \le 10^9\)），分别表示图的点数、边数和目标魔力值。保证 \(1\) 号点的药水魔力效果 \(a_1\) 的所有质因数均存在于 \(V\) 的质因数集合中。

第二行包含 \(n\) 个正整数 \(a_1, a_2, \dots, a_n\) （\(1 \le a_i \le 10^9\)），表示每个节点上药水的魔力效果。

接下来 \(m\) 行，每行包含三个整数 \(u, v, w\) （\(1 \le u, v \le n\)， \(1 \le w \le 10^9\)），表示节点 \(u\) 和 \(v\) 之间有一条耗费时间为 \(w\) 的权值边。图中可能存在重边或自环。

输出格式

对于每组测试数据，输出一行一个整数，表示使魔力值恰好等于 \(V\) 所需的最少时间。如果无法达到该目标，输出 -1。

样例输入

1
3 2 18
2 3 4
1 2 10
2 3 20

样例输出

0