Travel Support

G: Travel Support-Travel Support-

story

I, Honoka Kosaka, 16 years old! I'm a student idol! !!

In order to give a live performance to convey the goodness of student idols to everyone, we invite many student idols to perform live at Akiba Stadium.

However, some live participants come from afar and it costs a lot of train fare. That's why I decided to work part-time as a member of u ’s and give the train fare to the live participants! However, because the part-time job fee is late, it may not be possible to give the train fare in time for the departure of the live participants, or the part-time job fee may not be enough to give the full amount of the train fare. In such a case, I ask the live participants to prepare enough money in advance, but how much should I prepare?

So I want you to ask for the minimum amount that a live participant needs to have!

Mai-chan, rent a train?

problem

There are N cities, each numbered from 1 to N. The i (1 ≤ i ≤ N) th city has a population of t_i (t_i ≠ t_j if i ≠ j).

Currently, K live participants are about to gather in City 1. There are M ways of transportation allowed, and the i-th transportation can move between cities a_i and city b_i (1 ≤ a_i, b_i ≤ N) in both directions at the cost of c_i yen. It takes one day to travel by any means of transportation.

The i (1 ≤ i ≤ K) th participant departs from city x_i and heads for city 1 on a route that minimizes the cost required. If there are multiple routes with the lowest cost, select the route with the least number of travel days. If there are still multiple routes, choose a route that gives priority to moving to a city with a small population. Since this will determine the route and the number of days until arrival, each participant will start moving so that they will arrive at City 1 on the day of the live performance.

It is also known that the i (1 ≤ i ≤ K) th participant will be paid p_i yen d_i days before the live performance. As much as possible, the expenses paid will be used for movement after payment, but each participant must prepare in advance the costs incurred before payment and the costs after payment that cannot be covered.

Find the minimum cost that each participant will prepare in advance.

Input format

The input is given in the following format.

N M t_1 ... t_N a_1 b_1 c_1 ... a_M b_M c_M K x_1 d_1 p_1 ... x_K d_K p_K

Two integers N (1 ≤ N ≤ 100,000) and M (0 ≤ M ≤ 500,000) are given on the first line, separated by blanks, and represent the number of cities and the number of modes of transportation allowed, respectively. The second line is given N integers t_i (1 ≤ i ≤ N, 1 ≤ t_i ≤ 500,000) separated by blanks. t_i represents the population of city i, and if i ≠ j, then t_i ≠ t_j is satisfied.

The following M line is the input for the means of transportation, and three integers a_i, b_i, and c_i are given for the i-th means of transportation, separated by blanks. This means that the i-th means of transportation can travel between cities a_i and b_i (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) and costs c_i (1 ≤ c_i ≤ 10,000) yen. Also, there is no more than one means of transportation that directly connects any two cities. All cities can travel to and from each other using several modes of transportation.

The next line is given the integer K (1 ≤ K ≤ 100,000), which represents the number of participants.

The following K line is the input for the participants, and three integers x_i, d_i, p_i are given for the i-th participant, separated by blanks. This means that the i-th participant is initially in the city x_i (1 ≤ x_i ≤ N) and will be paid p_i (0 ≤ p_i ≤ 100,000) yen one day before the live d_i (0 ≤ d_i ≤ 100,000). Represent.

Output format

Output the minimum cost prepared by each participant in advance, starting with the first participant, separated by line breaks.

Since the input / output can be very large, it is recommended to use a high-speed input / output function.

Input example 1

5 6 100 80 70 60 50 1 2 500 2 5 100 1 3 400 1 4 200 3 5 700 4 5 800 1 5 3 600

Output example 1

0

The minimum cost for the entire trip is 600 yen, and you can reach City 1 in 2 days. There is no need to prepare the cost in advance as the cost will be paid 3 days in advance.

Input example 2

5 6 400 200 500 300 100 1 2 500 2 5 100 1 3 400 1 4 200 3 5 200 4 5 800 1 5 1 800

Output example 2

100

There are two routes with the lowest cost and the smallest number of days, 5-2-1 and 5-3-1. When moving from city 5 to the next city, city 2 is more important than city 3. Since the population is smaller, route 5-2-1 is selected. The total cost can be paid in full with the payment amount of 600 yen, but the cost before the payment must be reimbursed, so it is necessary to prepare only 100 yen, which is the cost between 5-2.

Input example 3

10 13 100 90 80 70 60 50 40 30 20 10 1 2 5 1 4 4 2 3 3 3 5 2 4 5 6 4 6 7 4 7 2 5 8 1 5 9 8 6 7 10 6 9 7 6 10 3 7 10 10 Ten 2 0 0 2 1 3 3 0 100000 3 1 3 3 1 100000 3 2 100000 3 100000 100000 8 1 5 9 2 11 10 0 0

Output example 3

Five 2 8 Five 3 0 0 7 7 14

Example

Input

5 6 100 80 70 60 50 1 2 500 2 5 100 1 3 400 1 4 200 3 5 700 4 5 800 1 5 3 600

Output

0

inputFormat

Input format

The input is given in the following format.

N M t_1 ... t_N a_1 b_1 c_1 ... a_M b_M c_M K x_1 d_1 p_1 ... x_K d_K p_K

Two integers N (1 ≤ N ≤ 100,000) and M (0 ≤ M ≤ 500,000) are given on the first line, separated by blanks, and represent the number of cities and the number of modes of transportation allowed, respectively. The second line is given N integers t_i (1 ≤ i ≤ N, 1 ≤ t_i ≤ 500,000) separated by blanks. t_i represents the population of city i, and if i ≠ j, then t_i ≠ t_j is satisfied.

The following M line is the input for the means of transportation, and three integers a_i, b_i, and c_i are given for the i-th means of transportation, separated by blanks. This means that the i-th means of transportation can travel between cities a_i and b_i (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) and costs c_i (1 ≤ c_i ≤ 10,000) yen. Also, there is no more than one means of transportation that directly connects any two cities. All cities can travel to and from each other using several modes of transportation.

The next line is given the integer K (1 ≤ K ≤ 100,000), which represents the number of participants.

The following K line is the input for the participants, and three integers x_i, d_i, p_i are given for the i-th participant, separated by blanks. This means that the i-th participant is initially in the city x_i (1 ≤ x_i ≤ N) and will be paid p_i (0 ≤ p_i ≤ 100,000) yen one day before the live d_i (0 ≤ d_i ≤ 100,000). Represent.

outputFormat

Output format

Output the minimum cost prepared by each participant in advance, starting with the first participant, separated by line breaks.

Since the input / output can be very large, it is recommended to use a high-speed input / output function.

Input example 1

5 6 100 80 70 60 50 1 2 500 2 5 100 1 3 400 1 4 200 3 5 700 4 5 800 1 5 3 600

Output example 1

0

The minimum cost for the entire trip is 600 yen, and you can reach City 1 in 2 days. There is no need to prepare the cost in advance as the cost will be paid 3 days in advance.

Input example 2

5 6 400 200 500 300 100 1 2 500 2 5 100 1 3 400 1 4 200 3 5 200 4 5 800 1 5 1 800

Output example 2

100

There are two routes with the lowest cost and the smallest number of days, 5-2-1 and 5-3-1. When moving from city 5 to the next city, city 2 is more important than city 3. Since the population is smaller, route 5-2-1 is selected. The total cost can be paid in full with the payment amount of 600 yen, but the cost before the payment must be reimbursed, so it is necessary to prepare only 100 yen, which is the cost between 5-2.

Input example 3

10 13 100 90 80 70 60 50 40 30 20 10 1 2 5 1 4 4 2 3 3 3 5 2 4 5 6 4 6 7 4 7 2 5 8 1 5 9 8 6 7 10 6 9 7 6 10 3 7 10 10 Ten 2 0 0 2 1 3 3 0 100000 3 1 3 3 1 100000 3 2 100000 3 100000 100000 8 1 5 9 2 11 10 0 0

Output example 3

Five 2 8 Five 3 0 0 7 7 14

Example

Input

5 6 100 80 70 60 50 1 2 500 2 5 100 1 3 400 1 4 200 3 5 700 4 5 800 1 5 3 600

Output

0

样例

5 6
100 80 70 60 50
1 2 500
2 5 100
1 3 400
1 4 200
3 5 700
4 5 800
1
5 3 600

0