The city is in the form of a graph and there are \(N\) junctions that are connected by \(M\) bidirectional roads. The time taken to travel on the \(i^{th}\) road is \(t_i\). Your house is located at the junction with index \(s\), whereas your storeroom is at junction \(d\). There are several chocolate shops in the city. In the case of any chocolate shortage, shop workers are dispatched from all the police stations immediately.
You are required to determine the least amount of time in which you can reach the storerooms after coming from your house without being intercepted by any staff of chocolate shops at any junction of the city.

Note: Workers can only intercept you at any of the junctions in the city.

Input format

First line: A single integer \(T\) denoting the number of test cases
For each test case:
- First line: An integer \(N\) denoting the number of junctions
- Second line: \(N\) space-separated integers
  Note: If the \(i^{th}\) integer is \(1\), then it means that the \(i^{th}\) has chocolate shops. Otherwise, it is \(0\).
- Next line: Two integers \(s\) and \(d\) denoting the junction of the house and the storeroom respectively
- Next line: Two integers \(M\) and \(3\) denoting the number of roads in your city and the number of columns in the input
- Next \(M\) lines: Three space-separated integers \(u\), \(v\), and \(t\), where \(u\) and \(v\) are the numbers of the cities connected by this road and \(t\) is the time taken to travel on that road
  Note: Input contains self-loops and multiple roads between two junctions.

Output format

For each test case, print a single integer denoting the least amount of time in which you can reach your storeroom avoiding the shop workers. If no such path exists, then print \(-1\).

Constraints

\(1 \le T \le 10\)

\(1 \le N, M \le 10^5\)

\(1 \le s, d \le N\)

\(1 \le u, v \le N\)

\(1 \le t \le 10^9\)