最短？路径

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

题目描述

给定一个 $n$ 个点 $m$ 条边的无向图，LH 打算从点 $1$ 出发去点 $n$ 。

假如 LH 到达了一个点 $i$ ，那么他可以选择在这个点花费 $a_i$ 的时间休息后继续赶路，或者不休息然后花费 $1$ 的时间简单整顿后继续赶路。

LH 不能连续超过 $k$ 个节点不休息，问从 $1$ 到 $n$ 的最短时间。

注意：假如 LH 到达了点 $n$ 也需要选择休息或者不休息。

输入描述:

第一行输入一个整数 ，表示测试用例组数。接下来是  个测试用例。

每个测试用例第一行包含三个整数 。 

第二行输入  个整数 ，表示在第  个点休息需要花费的时间。

随后  行每行两个整数 ，表示  和  之间有一条无向边。

保证输入的图联通，没有重边和自环。

保证所有测试用例  的和不超过 ， 的和不超过 。

输出描述:

对于每个测试用例，输出一个整数，表示 LH 从  到  的最短时间。

示例1

输入

复制

输出

复制

说明

一种可能的最优方案为 。

其中点  和点  不休息，在点  休息，总时间为 。

示例2

输入

复制

2
20 30 8
9 10 2 8 1 6 7 10 6 10 7 0 0 3 4 0 7 9 4 3
18 4
8 10
17 6
11 3
7 4
7 14
3 8
10 19
16 8
11 4
13 14
17 14
4 15
12 5
12 17
16 9
5 20
7 2
1 4
10 5
14 15
3 5
17 8
16 6
9 10
16 17
4 2
17 20
10 7
16 1
20 30 3
2 0 2 2 9 6 7 2 5 3 7 1 8 8 8 3 1 0 8 9
1 17
11 8
17 16
14 19
7 6
3 4
10 15
4 9
14 18
20 5
7 8
18 10
3 6
7 1
5 14
13 5
14 3
15 2
12 13
7 3
6 18
2 10
9 3
1 14
11 4
3 17
14 10
7 14
13 8
6 5

输出

复制

3
5