Uber HCVs (High Capacity Vehicles) runs across the city of UberLand. UberLand has N stops
where the HCVs pickup or drop the passengers. There is a network of M bidirectional roads that
connects various stops. Each road has a
particular length attached to it. -The Uber developers have introduced a weird feature of credits
where each stop has some assigned credits C[i] (0<=¡<N) which the HCV can collect when it
reaches the stop. These credits are used
to travel on a road and number of credits used for travelling on a road is equal to the length of the
road. So a HCV can travel on a road if it has credits equal or more than the length of the road.
Input:
Each test case has several lines. The first line contains an integer N which represent the number of
stops in UberLand.
The second line contains an array C of N integers which represents credits for each stop.
The third line contains an integer M which represent the number of roads in ÜberLand.
Then the following M lines each contain three integers X (0<=X<N) , Y (0<=Y<N) Z (1<=Z<=100)
which means there is road connecting stops X and Y with length Z where X I= Y
Then the last 2 lines contains one integer respectively, S and D which destination stop D (0<=D<N)
with
minimum distance travelled. Since you are a software developer yourself you think of writing a
program to calculate the minimum distance that you need to travel or return -1 if there is no way
possible. Assume the HCV starts at the source stop S and has credits aqual to the credits of S at
the start.

Input:
Each test case has several lines.
The first line contains an integer N which represent the number of stops in UberLand.
The second line contains an array C of N integers which represents credits for each stop.
The third line contains an integer M which represent the number of roads in UberLand.
Then the following M lines each contain three integers X (0<=X<N) ,Y (0<=Y<N) Z
(1<=Z<=100) which means there is road connecting stops X and Y with length Z.

Constraints
1 <=N<=50
0<=M<=100
0<=C[<=100
1<=Length of each road<=100

Input :
5
2 10 5 100 3
8
0 1 2
0 3 5
0 2 1
1 3 10
1 4 15
2 3 7
2 4 90
3 4 80
4
Output
19