#include <iostream>#include <algorithm>#include <cstdio>using namespace std;const int Mod=1000;struct Matrax {	int m[25][25];};Matrax a,per;int n,m;void initial(){	memset(a.m,0,sizeof(a.m));	memset(per.m,0,sizeof(per.m));	for(int i=0;i<n;i++)	per.m[i][i]=1;}Matrax multi(Matrax ae,Matrax b){	Matrax c;	for(int i=0;i<n;i++){		for(int j=0;j<n;j++){			c.m[i][j]=0;			for(int k=0;k<n;k++)			c.m[i][j]=(c.m[i][j]+ae.m[i][k]*b.m[k][j])%Mod;		}	}	return c;}int Power(int u,int v,int k){	Matrax ans=per,p=a;	while(k){		if(k&1){			ans=multi(ans,p);		}		k>>=1;		p=multi(p,p);	}	return ans.m[u][v];}int main(){	int u,v,k;	while(scanf("%d%d",&n,&m)!=EOF){		if(n==0&&m==0) break;		initial();		for(int i=0;i<m;i++){			scanf("%d%d",&u,&v);			a.m[u][v]=1;		}		int T;		scanf("%d",&T);		for(int i=0;i<T;i++){			scanf("%d%d%d",&u,&v,&k);			int ans=Power(u,v,k);			printf("%d\n",ans);		}	}	return 0;}