#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<uint64, int> P;

inline int bsr(uint64 x) {
  if (x == 0) return -1;
  return 63-__builtin_clzll(x);
}

struct RadixHeap {
  vector<P> v[65];
  uint64 last, sz;
  RadixHeap() {
    last = sz = 0;
  }
  inline void push(uint64 x, int p) {
    assert(last <= x);
    sz++;
    v[bsr(x^last)+1].push_back(P(x, p));
  }
  inline void push(P p) {
    push(p.first, p.second);
  }
  inline P top() {
    return pop(false);
  }
  inline P pop(bool f = true) {
    assert(sz);
    if (!v[0].size()) {
      int i = 1;
      while (!v[i].size()) i++;
      last = min_element(v[i].begin(), v[i].end())->first;
      for (P p: v[i]) {
        v[bsr(p.first^last)+1].push_back(p);
      }
      v[i].clear();
    }
    P r = v[0].back();
    if (f) {
      sz--;
      v[0].pop_back();
    }
    return r;
  }
  inline int size() {
    return sz;
  }
  inline bool empty() {
    return sz == 0;
  }
  inline void clear() {
    last = sz = 0;
    for (int i = 0; i < 33; i++) {
      v[i].clear();
    }
  }
};
typedef pair< int64, int64 > Pi;
struct edge
{
  int to, cost;
};
const int64 INF = 1LL << 60;
 
struct BinaryIndexedTree
{
  vector< int > data;
  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }
  int Query(int k)
  {
    int ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return(ret);
  }
  void Add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
 
int N, M;
vector< edge > graph[100000];
 
int64 Dijkstra(int s, int g, vector< int64 >& min_cost)
{
  RadixHeap Que;
  min_cost.assign(N, INF);
  Que.push(P(0, s));
  min_cost[s] = 0;
  while(!Que.empty()) {
    P p = Que.pop();
    if(p.second == g) return(p.first);
    if(min_cost[p.second] < p.first) continue;
    for(auto e : graph[p.second]) {
      if(p.first + e.cost < min_cost[e.to]) {
        min_cost[e.to] = p.first + e.cost;
        Que.push(P(min_cost[e.to], e.to));
      }
    }
  }
  return(-1);
}
 
 
int main()
{
  scanf("%d %d", &N, &M);
  for(int i = 0; i < M; i++) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    graph[A].push_back((edge){B, C});
    graph[B].push_back((edge){A, C});
  }
 
  vector< int64 > toS, toG;
  Dijkstra(0    , -1, toS);
  Dijkstra(N - 1, -1, toG);
 
  vector< Pi > Start(N);
  for(int i = 0; i < N; i++) Start[i] = Pi(toS[i], i);
  sort(Start.begin(), Start.end());
 
  vector< int64 > nums(toG);
  nums.push_back(-1);
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
  for(int i = 0; i < N; i++) {
    toG[i] = lower_bound(nums.begin(), nums.end(), toG[i]) - nums.begin();
  }
 
  int Q;
  scanf("%d", &Q);
  vector< pair< Pi, int > > Query(Q);
  for(int i = 0; i < Q; i++) {
    scanf("%lld %lld", &Query[i].first.first, &Query[i].first.second);
    Query[i].second = i;
  }
  sort(Query.begin(), Query.end());
 
  int ptr = 0;
  vector< int > ret(Q);
  BinaryIndexedTree bit(nums.size());
  for(int i = 0; i < Q; i++) {
    const Pi& q = Query[i].first;
    while(ptr < N && q.first >= Start[ptr].first) {
      bit.Add(toG[Start[ptr].second], 1);
      ++ptr;
    }
    int tail = lower_bound(nums.begin(), nums.end(), q.second) - nums.begin();
    ret[Query[i].second] = bit.Query(nums.size() - 1) - bit.Query(tail - 1); 
  }
 
  for(int i = 0; i < Q; i++) {
    printf("%d\n", ret[i]);
  }
}

Measured memory_bytes: 16036