题目描述

2026 马年新春，城郊百花盛放。郊外共有 \(n\) 处赏花胜地（编号 \(1, 2, \cdots, n\)），其间由 \(m\) 条道路相连。第 \(i\) 条道路双向连接胜地 \(x_i\) 与 \(y_i\)，骑马通行需消耗 \(w_i\) 点体力。每处胜地都有一个花韵值 \(a_i\)。

一条赏花路线 \(v_1, v_2, \ldots, v_c\) 是一条简单路径，即相邻胜地由道路直接相连，且每处胜地至多经过一次。路线的体力消耗为途经所有道路的体力值之和，花韵总值为 \(a_{v_1} + a_{v_2} + \cdots + a_{v_c}\)。

给定正整数 \(k\)，若一条赏花路线的花韵总值恰好是 \(k\) 的倍数，则称其为雅致路线。请找出体力消耗最小的雅致路线，或报告不存在这样的路线。

输入格式

本题有多组测试数据。第一行输入 \(T\ (1 \le T \le 10)\)，表示数据组数。

对于每组数据：

第一行输入三个整数 \(n, m, k\ (2 \le n \le 10^4, \ 1 \le m \le 10^4, \ 2 \le k \le 6)\)。

第二行输入 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\ (0 \le a_i < k)\)。

接下来 \(m\) 行，每行三个整数 \(x_i, y_i, w_i\ (1 \le x_i, y_i \le n, \ x_i \ne y_i, \ 1 \le w_i \le 10^9)\)，表示胜地 \(x_i\) 与 \(y_i\) 间一条体力消耗为 \(w_i\) 的双向道路。

保证图中无自环与重边。

输出格式

对于每组数据，输出一行一个整数——体力消耗最小的雅致路线的代价。若不存在雅致路线，输出 \(-1\)。

样例输入

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

样例输出

3
0
-1