#include<cstdio>

#include<cstring>

const int MOD=1000;

const int N=25;

struct matrix

{

    int s[N][N];

    matrix(){memset(s,0,sizeof(s));}

};

int n,m,T;

inline matrix mul(matrix a,matrix b)

{

    matrix res;

    for(register int i=0;i<n;i++)

        for(register int j=0;j<n;j++)

            for(register int k=0;k<n;k++)

                res.s[i][j]=(res.s[i][j]+(a.s[i][k]*b.s[k][j])%MOD)%MOD;

    return res;

}

inline matrix pow(matrix a,int b)

{

    matrix res;

    for(register int i=0;i<n;i++)res.s[i][i]=1;

    for(;b;b>>=1,a=mul(a,a))if(b&1)res=mul(res,a);

    return res;

}

int main()

{

    //freopen("input.in","r",stdin);

    while(scanf("%d%d",&n,&m)==2&&(n+m))

    {

        matrix map;

        for(register int i=1;i<=m;i++)

        {

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

            map.s[u][v]=1;

        }scanf("%d",&T);

        while(T--)

        {

            int u,v,k;

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

            matrix a;a=map;

            a=pow(a,k);printf("%d\n",a.s[u][v]%MOD);

        }

    }

    return 0;

}