#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#ifndef LIB_REPEAT_HPP
#define LIB_REPEAT_HPP
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_one(i,n) for (int i = 1; i <= (n); ++i)
#define repeat_rev(i,n) for (int i = (n)-1; 0 <= i; --i)
#define foreach(it, cont) for (decltype(cont.begin()) it = cont.begin(); it != cont.end(); ++it)
#endif
#ifndef LIB_GRAPH_DIJKSTRA_HPP
#define LIB_GRAPH_DIJKSTRA_HPP

#include <vector>
#include <queue>
#ifndef LIB_REPEAT_HPP
#define LIB_REPEAT_HPP
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_one(i,n) for (int i = 1; i <= (n); ++i)
#define repeat_rev(i,n) for (int i = (n)-1; 0 <= i; --i)
#define foreach(it, cont) for (decltype(cont.begin()) it = cont.begin(); it != cont.end(); ++it)
#endif
template <typename T>
std::vector<T> dijkstra(const std::vector<std::vector<std::pair<int,T> > > & g, int s) {
    int n = g.size();
    std::vector<T> result(n,-1);
    std::vector<bool> used(n, false);
    std::priority_queue<std::pair<T,int>, std::vector<std::pair<T,int> >, std::greater<std::pair<T,int> > > q;
    q.push(std::make_pair(0,s));
    while (not q.empty()) {
        T   c = q.top().first;
        int i = q.top().second;
        q.pop();
        if (not used[i]) {
            used[i] = true;
            result[i] = c;
            repeat (e,(int)g[i].size()) {
                int j = g[i][e].first;
                T   d = g[i][e].second;
                if (not used[j]) {
                    q.push(std::make_pair(c+d,j));
                }
            }
        }
    }
    return result;
}

#endif
#ifndef LIB_DATA_BINARY_INDEXED_TREE_HPP
#define LIB_DATA_BINARY_INDEXED_TREE_HPP

#include <vector>

template <typename T>
struct binary_indexed_tree {
    std::vector<T> v;
    binary_indexed_tree(int n) : v(n) {}

    void add(size_t i, T w) {
        for (size_t j = i+1; j <= v.size(); j += j & -j) v[j-1] += w;
    }
    void update(size_t i, T w) {
        add(i, w - v[i-1]);
    }
    int sum(size_t i) {
        T acc = 0;
        for (size_t j = i; 0 < j; j -= j & -j) acc += v[j-1];
        return acc;
    }
};

#endif
#ifndef LIB_TYPEDEF_LL_HPP
#define LIB_TYPEDEF_LL_HPP
typedef long long ll;
typedef unsigned long long ull;
#endif
#ifndef LIB_DEBUG_HPP
#define LIB_DEBUG_HPP
#ifdef DEBUG
#include <cassert>
#define debug(a) a
#else
#define debug(a)
#endif
#endif
using namespace std;

// a[nth(a)[i]] = sorted(a)[i]
template <typename T>
vector<int> nth(const vector<T> & g) {
    int n = g.size();
    vector<int> result(n);
    vector<pair<ll,int> > t(n);
    repeat (i,n) t[i] = make_pair(g[i],i);
    sort(t.begin(), t.end());
    repeat (i,n) result[i] = t[i].second;
    return result;
}

template <typename S, typename T>
vector<pair<S,T> > zip(const vector<S> & a, const vector<S> & b) {
    vector<pair<S,T> > c(max(a.size(),b.size()));
    repeat (i,(int)a.size()) c[i].first  = a[i];
    repeat (i,(int)b.size()) c[i].second = b[i];
    return c;
}
template <typename S, typename T>
pair<vector<S>,vector<T> > unzip(const vector<pair<S,T> > & c) {
    vector<S> a(c.size());
    vector<T> b(c.size());
    repeat (i,(int)c.size()) {
        a[i] = c[i].first;
        b[i] = c[i].second;
    }
    return make_pair(a,b);
}
template <typename S, typename T>
vector<S> firsts(const vector<pair<S,T> > & c) {
    vector<S> a(c.size());
    repeat (i,(int)c.size()) a[i] = c[i].first;
    return a;
}
template <typename S, typename T>
vector<T> seconds(const vector<pair<S,T> > & c) {
    vector<T> b(c.size());
    repeat (i,(int)c.size()) b[i] = c[i].second;
    return b;
}

template <typename T>
struct compresser {
    set<T> used;
    template <class InputIterator>
    void add(InputIterator first, InputIterator last) {
        for (; first != last; ++ first) {
            used.insert(*first);
        }
    }
    map<T,size_t> compress() const {
        typename std::map<T,size_t> result;
        int i = 0;
        auto it = used.begin();
        while (it != used.end()) result[*(it ++)] = i ++;
        return result;
    }
};

int main() {
    ios_base::sync_with_stdio(false);

    int N, M; cin >> N >> M;
    vector<vector<pair<int,ll> > > g(N);
    repeat (i,M) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    int Q; cin >> Q;
    vector<pair<ll,ll> > q(Q);
    repeat (i,Q) cin >> q[i].first >> q[i].second;

    vector<ll> ds = dijkstra(g, 0);
    vector<ll> dg = dijkstra(g, N-1); {
        vector<pair<ll,ll> > d = zip<ll,ll>(ds,dg);
        sort(d.begin(), d.end());
        auto p = unzip(d);
        ds = p.first;
        dg = p.second;
    }

    map<ll,size_t> comp; {
        compresser<ll> c;
        c.add(dg.begin(), dg.end());
        vector<ll> r = unzip(q).second;
        c.add(r.begin(), r.end());
        comp = c.compress();
    }

    binary_indexed_tree<int> bit(comp.rbegin()->second+1);

    vector<int> qth = nth(unzip(q).first);
    vector<int> result(Q);

    int j = 0;
    repeat (i,Q) {
        ll fs = q[qth[i]].first;
        int fg = comp[q[qth[i]].second];
        for (; j < N and ds[j] <= fs; ++j) {
            bit.add(comp[dg[j]],1);
        }
        result[qth[i]] = j - bit.sum(fg);
    }
    repeat (query,Q) cout << result[query] << endl;
    return 0;
}

Measured memory_bytes: 29304