#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN = ;

const int mod  = ;

struct Matrix

{///定义一个矩阵

    int edge[MAXN][MAXN];

};

int N;

void Mul(Matrix a, Matrix b, Matrix &ans)

{///a * b -> ans

    memset(ans.edge, , sizeof(ans.edge));

    for(int i=; i<N; i++)

    for(int j=; j<N; j++)

    for(int p=; p<N; p++)

    {

        ans.edge[i][j] += a.edge[i][p] * b.edge[p][j];

        ans.edge[i][j] %= mod;

    }

}

void QuickPow(Matrix Map, int k, Matrix &ans)

{///Map^k -> ans

    memset(ans.edge, , sizeof(ans.edge));

    for(int i=; i<N; i++)

        ans.edge[i][i] = true;

    while(k)

    {

        if(k & )

            Mul(ans, Map, ans);

        Mul(Map, Map, Map);

        k /= ;

    }

}

int main()

{

    int M;

    while(scanf("%d%d", &N, &M), M+N)

    {

        int u, v, k;

        Matrix Map, ans;

        memset(Map.edge, , sizeof(Map.edge));

        while(M--)

        {

            scanf("%d%d", &u, &v);

            Map.edge[u][v] = true;

        }

        scanf("%d", &M);

        while(M--)

        {

            scanf("%d%d%d", &u, &v, &k);

            QuickPow(Map, k, ans);

            printf("%d\n", ans.edge[u][v]);

        }

    }

    return ;

}