#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P = 1e3;
struct node {
    LL a[21][21];
    node() { memset(a, 0, sizeof a); }
};
int n, m;
node operator*(node A, node B) {
    node C;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % P;
    return C;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF && n && m) {
        node A[21];
        for (int i = 1; i <= n; i++) A[0].a[i][i] = 1;
        for (int i = 1, x, y; i <= m; i++) {
            scanf("%d%d", &x, &y); x++; y++;
            A[1].a[x][y] = 1;
        }
        for (int k = 2; k <= 20; k++) {
            A[k] = A[k - 1] * A[1];
        }
        int T; scanf("%d", &T);
        while (T--) {
            int x, y, k; scanf("%d%d%d", &x, &y, &k); x++; y++;
            printf("%d\n", A[k].a[x][y]);
        }
    }
    return 0;
}