Xzz is a child with severe procrastinations. The new semester begins, He still has a lot of homework to do. Now, he needs your help. As the best friend, you are good at math. So, you will help him do some math homework. Now Xzz wants to go to your home. You can regard the traffic network as a undirected graph with n nodes (numbered from 1 to n) and m edges.
Xzz’s home at node s, and your at node t. At each node i, there is a traffic light, and the traffic light change the status after ai, which means that you can only leave node i, at time[0, ai), [2 * ai, 3 * ai), [4 * ai, 5 * ai), … , [2k * ai, (2 * k + 1) * ai). If ai = 0 means there is no traffic light, you can leave at any time. And there are m edges, each edge means it will take Xzz vi time from node xi to node yi. Now Xzz wants to know how much time he will take to arrive your home.
First line of the input file contains an integer T(0 < ≤ 20) that indicates how many cases of inputs are there.
The description of each case is given below:
The first line of each case contains two numbers n, m, means there are n nodes and m edges.
(n ≤ 1000, m ≤ n(n-1) / 2)
Then follow n lines. In ith line there will be a number, ai.(ai ≤ 1000)
Then follow m lines. In ith line there will be three numbers, xi, yi and vi, means there is a edge between xi and yi, and Xzz take vi time to go trough this edge. vi ≤ 1000.
The last line contains two numbers s, t. It’s guarantee that there is at least one path between node s and t.
1 9 14 3 5 7 3 5 7 9 3 5 1 2 4 1 8 8 2 3 8 2 8 11 3 4 7 3 6 4 3 9 2 4 5 9 4 6 14 5 6 10 6 7 2 7 9 6 7 8 1 8 9 7 1 5
28