时间限制： 5.0 秒

空间限制： 256 MB

题目描述

某校新建的大楼中有 $n$ 台设备，学校需要利用这些设备搭建一个网络。我们用 $1$ 到 $n$ 的整数给这些设备编号。

这些设备之间一共可以建立 $m$ 条连线，建立每条连线会消耗一定的费用。连接建立后两台设备就可以相互通信了。两台设备可以借助其他设备进行通信，即通信关系可传递：如果设备 A 和设备 B 都能与设备 C 相互通信，那么设备 A 和设备 B 也能相互通信。

由于大楼的拓扑结构所限，可以建立连线的两台设备，一定满足其编号之差的绝对值不超过 $p$。

这 $n$ 台设备中的一部分属于用户设备。学校要求在最终的网络中，用户设备必须两两能够相互通信，其他设备则可以根据需要选择连线或不连线。

现在问要达到学校的要求最少要消耗多少的费用。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$，表示数据的组数，保证 $T\le 5$。接下来依次描述每组数据。

每组数据的第一行包含三个正整数 $n, m, p$，表示设备的总数，可以建立的连线数量和拓扑结构的参数。

第二行包含一个长度为 $n$ 的 01 字符串，依次表示这 $n$ 台设备是否为用户设备；为 1 表示是，为 0 表示不是。相邻字符之间无空格隔开，保证不会出现除了 0 和 1 之外的字符。保证至少有 $2$ 个设备是用户设备。

接下来 $m$ 行，每行包含三个非负整数 $u, v, w$，表示设备 $u$ 和设备 $v$ 可以消耗 $w$ 的费用建立连线。其中 $1\le u < v ≤ n,~1\le v – u ≤ p,~0\le w ≤ 10^6$。

除第二行外，所有的数之间用一个空格隔开。

保证两台设备之间最多只有一条可以建立的连线，保证至少存在一种方案能够满足学校的要求。

输出格式

输出到标准输出。

对于每组数据，输出一行一个整数，表示能达到要求所需的最少费用。

1
20 11 6
10000100001100000000
1 6 300
1 3 100
3 6 100
4 10 100
4 6 100
6 10 400
10 15 100
11 15 100
10 11 500
12 15 100
15 20 100

700

样例 1 解释

用户设备分别是 $1,6,11,12$。最优的方案需要选择以下连线：设备 $1$ 和 $3$，费用 $100$；设备 $3$ 和 $6$，费用 $100$；设备 $4$ 和 $6$，费用 $100$；设备 $4$ 和 $10$，费用 $100$；设备 $10$ 和 $15$，费用 $100$；设备 $11$ 和 $15$，费用 $100$；设备 $12$ 和 $15$，费用 $100$。共计 $700$。

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于所有数据，保证 $1\le n\le 500,~2\le c\le n,~1\le p\le 6$（其中 $c$ 为用户设备总数）。

子任务 1（97 分）：传统计分，每组测试点满足以下限制：

子任务 2（3 分）：捆绑测试，Hack 数据，无特殊限制。