#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1LL<<61
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge {
	int from,to;
	ll cost;

	edge(int t,ll c) : to(t),cost(c) {}
	edge(int f,int t,ll c) : from(f),to(t),cost(c) {}

	bool operator<(const edge &e) const {
		return cost < e.cost;
	}
};

vector<edge> G[100005];
ll d[100005], d2[100005];

void dijkstra(int s, int n) {
	priority_queue<pair<ll, ll> , vector<pair<ll, ll> >, greater<pair<ll, ll> > > que;
	fill(d, d+n, INF);

	d[s] = 0;
	que.push(P(0,s));

	while(que.size()) {
		P p = que.top();
		que.pop();

		int v = p.second;
		if(d[v] < p.first) continue;

		rep(i, G[v].size()) {
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

struct BIT {
	vector<int> bit;

	BIT(int n) : bit(n+1) {}

	int sum(int i) {
		int s = 0;
		while(i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}

	void add(int i,int x) {
		while(i <= bit.size()) {
			bit[i] += x;
			i += i & -i;
		}
	}
};

int main() {
	int n, m;
	cin >> n >> m;

	rep(i, m) {
		ll a, b, c;
		cin >> a >> b >> c;

		G[a].push_back(edge(b, c));
		G[b].push_back(edge(a, c));
	}

	dijkstra(n-1, n);
	memset(d2, 0, sizeof(d2));
	rep(i, n) {
		d2[i] = d[i];
	}

	dijkstra(0, n);

	vector<ll> d3(n);
	vector<pair<ll, int> > D, D2;
	rep(i, n) {
		d3[i] = d[i];
		D.push_back(mp(d[i], i));
		D2.push_back(mp(d2[i], i));
	}

	sort(d3.begin(), d3.end());
	sort(D.begin(), D.end());
	sort(D2.begin(), D2.end());

	// cout << "-------- D1:" << endl;
	// rep(i, n) {
	// 	cout << "i:" << i << "| " << D[i].first << " " << D[i].second << endl;
	// }
	//
	// cout << "-------- D2:" << endl;
	// rep(i, n) {
	// 	cout << "i:" << i << "| " << D2[i].first << " " << D2[i].second << endl;
	// }

	map<int, int> ma;
	rep(i, n) {
		ma[ D[i].second ] = i;
	}

	// cout << "-------- map D1:" << endl;
	// rep(i, n) {
	// 	cout << i << " " << ma[i] << endl;
	// }

	int q;
	cin >> q;

	vector<pair<pair<ll, ll> , int> > query(q);

	rep(i, q) {
		ll s, g;
		cin >> s >> g;

		query[i] = mp(mp(g, s), i);
	}

	sort(query.begin(), query.end());
	//
	// cout << "------ query:" << endl;
	// rep(i, q) {
	// 	cout << "i:" << i << "| ";
	// 	cout << query[i].first.first << " " << query[i].first.second << " " << query[i].second << endl;
	// }

	BIT bit(n + 5);
	vector<P> ans;
	int start = 0;
	rep(i, q) {
		ll s = query[i].first.second;
		ll g = query[i].first.first;
		int id = query[i].second;

		for(; start < n; start++) {
			if(g > D2[start].first) {
				int k = ma[ D2[start].second ];
				bit.add(k + 1, 1);
				continue;
			} else break;
		}

		vector<ll>::iterator ite = upper_bound(d3.begin(), d3.end(), s);
		int k = ite - d3.begin() - 1;
		if(k < 0) {
			ans.push_back(mp( id, 0));
		} else {
			int res = k + 1;
			
			// cout << "---------------- i : " << i << "   id:" << id << endl;
			// cout << "query:" << s << " " << g << endl;
			// cout << "k:" << k << endl;
			// cout << "ma[k]:" << ma[k] << endl;
			// cout << "res:" << res << endl;
			// cout << "bit:" << bit.sum(ma[k] + 1) << endl;
			// cout << "start:" << start << endl;
			res -= bit.sum(k + 1);
			// cout << "push:" << res << endl;
			ans.push_back(mp( id, res));
		}
	}

	sort(ans.begin(), ans.end());

	rep(i, ans.size()) {
		cout << ans[i].second << endl;
	}

	return 0;
}

Measured memory_bytes: 23380