K-对潇潇暮雨洒江天，一番洗清秋_第十八届西南科技大学ACM程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

行于荆路，志岂可无；重整旗鼓，终遇前途。我们把这个旅途看作一个二维平面，则一原点建立一个笛卡尔坐标系。坐标系内有以下物体："元"、"迹"、"驻"。

①："元"是一个看作以原点为圆心的圆。平面中有 $n$ 个"元"，每个"元"的半径是是 $1$ ~ $n$ 的整数，且任意两"元"的半径不同。

②："驻"是"元"上的点。平面中有 $n$ 个"驻"，第 $i$ 个（编号从 $1$ 开始）"驻"所在的"元"的半径是 $1$ ~ $n$ 的整数。

③："迹"是两个"驻"的线段。一般的，若两个"驻"所在的"元"的半径相差 $2$ ，则在这两个"驻"之间存在一条"迹"，移动一次花费 $p$ 点体力值，即从某一个"驻"移动到另外一个"驻"需要花费 $p$ 点体力值，从另一个"驻"移动到这个"驻"也需要花费 $p$ 点体力值；若两个"驻"所在的“元”相差 $1$ ，则在这两个"驻"之间也存在一条"迹"，移动一次花费 $2\times p$ 点体力值。此外，平面中还有有 $m$ 条"迹"，第 $j$ 条"迹"的两个"驻"的编号分别是 $u_j$ 、 $v_j$ （保证这两个"驻"的编号不同），只要存在"迹"，则可以在这两"驻"之间移动，移动一次的花费为 $w_j$ 点体力值。若两个"驻"之间没有"迹"，则不能在它们之间移动。

④：特别的，我们规定：把半径为 $1$ 的"元"称为"始元"，对于"始元"上的任意一个"驻"，无法从其他"驻"移动到该"驻"；把半径为 $n$ 的"元"称为"末元"，对于从"末元"上的任意一个"驻"，无法从该"驻"移动到其他"驻"。

现在，你开始有 $s$ 点体力值，如果你能从"始元"上的任意"驻"到"末元"上的任意"驻"且剩余体力不少于 $0$ ，求最大的剩余体力值，如果不存在输出 $-1$ 。

输入描述:

第一行输入一个正整数 ，表示测试样例组数；

对于每组测试样例，

第一行输入四个整数 ，，，，具体参见描述；

接下来一行输入  个正整数 ，表示第  个"驻"所在的"元"的半径；

接下来  行，每行输入三个正整数  ，（），，表示第  条"迹"的两个端点的编号以及在这两个端点间移动一次的花费。

输出描述:

输出  行，每行输出一个整数，如果存在方案，则输出这个方案的所剩余的最大体力值，否则输出 。

示例1

输入

复制

2
8 3 3 100
6 8 7 5 1 3 3 3
1 7 1
7 8 1
5 8 1
3 1 6 5
2 3 1
2 3 6

输出

复制

94
-1

说明


样例输入的第一组样例如上图所示，最终的路径为 ，总共需要花费  点体力值，所以最终输出 。