#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define HUGE_NUM 99999999999999
#define NUM 100005

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

struct Query{
	Query(ll arg_from_start,ll arg_from_goal,int arg_index){
		from_start = arg_from_start;
		from_goal = arg_from_goal;
		index = arg_index;
	}
	bool operator<(const struct Query &arg) const{
		return from_start < arg.from_start;
	}
	ll from_start,from_goal;
	int index;
};

struct Info{
	Info(int arg_node_id,ll arg_sum_cost){
		node_id = arg_node_id;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{
		return sum_cost > arg.sum_cost;
	}
	int node_id;
	ll sum_cost;
};

struct Data{
	bool operator<(const struct Data &arg) const{
		return dist_from_start < arg.dist_from_start;
	}
	ll dist_from_start;
	int dist_from_goal_pos;
};


int N,M,SIZE;
int BIT[NUM],ans[NUM];
ll min_dist_from_start[NUM],min_dist_from_goal[NUM];
vector<Edge> G[NUM];
vector<ll> WORK;
vector<Query> query;
Data data[NUM];

void add(int loc,int value){

	BIT[loc] += value;

	loc += loc & -loc;

	while(loc <= SIZE){
		BIT[loc] += value;
		loc += loc & -loc;
	}
}

int getSum(int loc){

	int sum = BIT[loc];

	loc -= loc & -loc;

	while(loc > 0){
		sum += BIT[loc];
		loc -= loc & -loc;
	}
	return sum;
}


int main(){

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

	int from,to;
	ll cost;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %lld",&from,&to,&cost);
		G[from].push_back(Edge(to,cost));
		G[to].push_back(Edge(from,cost));
	}

	int num_query;
	scanf("%d",&num_query);

	ll fs,fg;

	for(int i = 0; i < num_query; i++){
		scanf("%lld %lld",&fs,&fg);
		query.push_back(Query(fs,fg,i));
	}

	for(int i = 0; i < N; i++)min_dist_from_start[i] = HUGE_NUM;
	min_dist_from_start[0] = 0;

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

	while(!Q.empty()){

		if(Q.top().sum_cost > min_dist_from_start[Q.top().node_id]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				if(min_dist_from_start[G[Q.top().node_id][i].to] > Q.top().sum_cost+G[Q.top().node_id][i].cost){
					min_dist_from_start[G[Q.top().node_id][i].to] = Q.top().sum_cost+G[Q.top().node_id][i].cost;
					Q.push(Info(G[Q.top().node_id][i].to,min_dist_from_start[G[Q.top().node_id][i].to]));
				}
			}
			Q.pop();
		}
	}

	for(int i = 0; i < N; i++)min_dist_from_goal[i] = HUGE_NUM;
	min_dist_from_goal[N-1] = 0;

	Q.push(Info(N-1,0));

	while(!Q.empty()){

		if(Q.top().sum_cost > min_dist_from_goal[Q.top().node_id]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				if(min_dist_from_goal[G[Q.top().node_id][i].to] > Q.top().sum_cost+G[Q.top().node_id][i].cost){
					min_dist_from_goal[G[Q.top().node_id][i].to] = Q.top().sum_cost+G[Q.top().node_id][i].cost;
					Q.push(Info(G[Q.top().node_id][i].to,min_dist_from_goal[G[Q.top().node_id][i].to]));
				}
			}
			Q.pop();
		}
	}

	for(int i = 0; i < N; i++){
		data[i].dist_from_start = min_dist_from_start[i];
		WORK.push_back(min_dist_from_goal[i]);
	}

	sort(WORK.begin(),WORK.end());
	WORK.erase(unique(WORK.begin(),WORK.end()),WORK.end());

	int left,right,m;

	for(int i = 0; i < N; i++){
		left = 0,right = (int)WORK.size()-1,m = (left+right)/2;

		while(left <= right){
			if(WORK[m] == min_dist_from_goal[i]){
				data[i].dist_from_goal_pos = m;
				break;
			}else if(WORK[m] > min_dist_from_goal[i]){
				right = m-1;
			}else{
				left = m+1;
			}
			m = (left+right)/2;
		}
	}

	sort(query.begin(),query.end());
	sort(data,data+N);

	SIZE = WORK.size();

	for(int i = 0; i <= SIZE; i++)BIT[i] = 0;

	int near_small_index;

	int id = 0;
	for(int i = 0; i < num_query; i++){

		while(id < N && data[id].dist_from_start <= query[i].from_start){
			add(data[id].dist_from_goal_pos+1,1);
			id++;
		}

		left = 0,right = (int)WORK.size()-1,m = (left+right)/2;

		near_small_index = -1;
		while(left <= right){
			if(WORK[m] < query[i].from_goal){
				near_small_index = m+1;
				left = m+1;
			}else{
				right = m-1;
			}
			m = (left+right)/2;
		}
		if(near_small_index == -1){
			ans[query[i].index] = id;
			continue;
		}

		ans[query[i].index] = id-getSum(near_small_index);
	}

	for(int i = 0; i < num_query; i++){
		printf("%d\n",ans[i]);
	}

	return 0;
}



Measured memory_bytes: 18108