#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <tuple>
#include <set>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

const ll inf = 1LL << 60;

void dijkstra(int s, vector<vector<P>> &G, vector<ll> &Cost) {
    int n = G.size();
    Cost.assign(n, inf);
    Cost[s] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(0LL, s);
    while (pq.size()) {
        ll cost;
        int to;
        tie(cost, to) = pq.top();
        pq.pop();
        if (cost > Cost[to]) continue;
        for (auto p : G[to]) {
            ll ncost = p.first + cost;
            int nto = p.second;
            if (Cost[nto] > ncost) {
                Cost[nto] = ncost;
                pq.emplace(ncost, nto);
            }
        }
    }
}

class BIT {
public:
    vector<ll> data;
    BIT(int n) {
        int N = 1;
        while (N < n) {
            N *= 2;
        }
        data.resize(N, 0);
    }
    void update(int pos, ll val) {
        pos++;
        for (int p = pos; p < data.size(); p += (p & -p)) {
            data[p] += val;
        }
    }
    ll query(int pos) {
        ll ans = 0;
        pos++;
        for (int p = pos; p > 0; p -= (p & -p)) {
            ans += data[p];
        }
        return ans;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<P>> Graph(n);
    REP(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;
        Graph[a].push_back({c, b});
        Graph[b].push_back({c, a});
    }
    vector<P> Cost(n);
    {
        vector<ll> start, goal;
        dijkstra(0, Graph, start);
        dijkstra(n - 1, Graph, goal);
        REP(i, 0, n) {
            Cost[i] = {start[i], goal[i]};
        }
        sort(Cost.begin(), Cost.end());
    }

    int q;
    cin >> q;
    vector<P> F(q);
    REP(i, 0, q) {
        cin >> F[i].first >> F[i].second;
    }
    vector<int> indices(q);
    REP(i, 0, q) {
        indices[i] = i;
    }
    sort(indices.begin(), indices.end(), [&](int a, int b) {
        return F[a] < F[b];
    });

    int an = 0;
    // 座標圧縮
    {
        vector<ll> val;
        REP(i, 0, n) {
            val.push_back(Cost[i].second);
        }
        REP(i, 0, q) {
            val.push_back(F[i].second);
        }
        sort(val.begin(), val.end());
        val.erase(unique(val.begin(), val.end()), val.end());
        an = val.size();

        REP(i, 0, n) {
            Cost[i].second = lower_bound(val.begin(), val.end(), Cost[i].second) - val.begin();
        }
        REP(i, 0, q) {
            F[i].second = lower_bound(val.begin(), val.end(), F[i].second) - val.begin();
        }
    }

    BIT bit(an + 2);

    vector<int> ans(q, 0);
    int pos = 0;
    set<ll> s;
    REP(i, 0, q) {
        int v = indices[i];
        while (pos < n && Cost[pos].first <= F[v].first) {
            bit.update(Cost[pos].second, 1);
            pos++;
        }
        ans[v] = pos - bit.query(F[v].second - 1);
    }
    REP(i, 0, q) {
        cout << ans[i] << endl;
    }

    return 0;
}



Measured memory_bytes: 16848