Problem: 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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

struct Edge{
	Edge(int arg_to,ll arg_cost){
		to = arg_to;
		cost = arg_cost;
	}
	int to;
	ll cost;
};

struct Info{

	int start,day,pay;
};

struct State{

	State(int arg_node_id,int arg_sum_date,int arg_sum_cost){
		node_id = arg_node_id;
		sum_date = arg_sum_date;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct State &arg) const{

		if(sum_cost != arg.sum_cost){

			return sum_cost > arg.sum_cost; //総コストが異なるなら昇順(PQ)
		}else{

			return sum_date > arg.sum_date; //総コストが同じなら、日数の総和(PQ)
		}
	}

	int node_id,sum_date,sum_cost;
};

int N,E,K;
int root; //根ノードの番号
int MAX_LOG_V = 17;
int POW[18];
int T[NUM];
int min_dist[NUM],min_date[NUM];
int parent[18][NUM];
int depth[NUM];
vector<Edge> G[NUM]; //グラフの隣接リスト表現
vector<int> Tree_G[NUM];
Info info[NUM];


//parentとdepthを再帰的に設定
void dfs(int node_id,int parent_id,int d){
	parent[0][node_id] = parent_id;
	depth[node_id] = d;
	for(int i = 0; i < Tree_G[node_id].size(); i++){
		if(Tree_G[node_id][i] != parent_id)dfs(Tree_G[node_id][i],node_id,d+1);
	}
}

//初期化
void init(){
	//parent[0]とdepthを初期化する
	dfs(root,-1,0);
	//parentを初期化する
	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < N; node_id++){
			if(parent[k][node_id] < 0)parent[k+1][node_id] = -1; //node_idの2^k上のノードがルートノードより上なら、2^(k+1)上も同様とする
			else{
				parent[k+1][node_id] = parent[k][parent[k][node_id]];
			}
		}
	}
}


int main(){


	POW[0] = 1;
	for(int i = 1; i <= 17; i++){
		POW[i] = POW[i-1]*2;
	}

	scanf("%d %d",&N,&E);

	for(int i = 0; i < N; i++){

		scanf("%d",&T[i]);
	}

	int from,to,cost;

	for(int i = 0; i < E; i++){

		scanf("%d %d %d",&from,&to,&cost);
		from--;
		to--;

		G[from].push_back(Edge(to,cost));
		G[to].push_back(Edge(from,cost));
	}

	scanf("%d",&K);

	for(int i = 0; i < K; i++){

		scanf("%d %d %d",&info[i].start,&info[i].day,&info[i].pay);
		info[i].start--;
	}

	//ダイクストラ

	min_dist[0] = 0;
	min_date[0] = 0;

	for(int i = 1; i < N; i++){

		min_dist[i] = BIG_NUM;
		min_date[i] = BIG_NUM;
	}

	priority_queue<State> Q;
	Q.push(State(0,0,0));

	int next_node,next_cost,next_date;

	while(!Q.empty()){

		if((Q.top().sum_cost > min_dist[Q.top().node_id])
				|| (Q.top().sum_cost == min_dist[Q.top().node_id] && Q.top().sum_date > min_date[Q.top().node_id])){

			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){

				next_node = G[Q.top().node_id][i].to;
				next_cost = Q.top().sum_cost+G[Q.top().node_id][i].cost;
				next_date = Q.top().sum_date+1;

				if(min_dist[next_node] > next_cost){

					min_dist[next_node] = next_cost;
					min_date[next_node] = next_date;
					Q.push(State(next_node,next_date,next_cost));

				}else if(min_dist[next_node] == next_cost && min_date[next_node] > next_date){

					min_date[next_node] = next_date;
					Q.push(State(next_node,next_date,next_cost));
				}
			}
			Q.pop();
		}
	}

	int tmp_num,next;

	//最短経路の辺を張る
	for(int i = 1; i < N; i++){
		//次の節店を探し、辺を張る
		tmp_num = BIG_NUM;
		next = -1;

		for(int k = 0; k < G[i].size(); k++){
			if(min_dist[i]-G[i][k].cost == min_dist[G[i][k].to] && min_date[i] == min_date[G[i][k].to]+1){ //最短経路上

				if(tmp_num > T[G[i][k].to]){ //人口で選ぶ
					tmp_num = T[G[i][k].to];
					next = G[i][k].to;
				}
			}
		}

		if(next == -1)continue;

		Tree_G[next].push_back(i); //木は都市0をスタートとする
	}

	//木作り&ダブリング
	root = 0;
	init();

	int current_node,diff;

	for(int i = 0; i < K; i++){

		int ans = BIG_NUM;

		current_node = info[i].start;
		diff = depth[info[i].start]-info[i].day;

		for(int k = MAX_LOG_V-1; k >= 0; k--){
			if(diff >= POW[k]){ //たとえば深さの差が39なら、32+4+2+1のように、ノードを上方に移動させる

				current_node = parent[k][current_node];
				diff -= POW[k];
			}
		}

		if(current_node == -1){ //★金を貰う前に着く★

			ans = min(ans,min_dist[info[i].start]);

		}else{

			ans = min(ans,(min_dist[info[i].start]-min_dist[current_node])+max(0,min_dist[current_node]-info[i].pay));
		}

		printf("%d\n",ans);
	}

	return 0;
}