题意：略
直接矩阵乘法就行了
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL __int64
#define N 30
int n,m;
struct node{
int mat[N][N];
node operator *(const node &x){
node tmp;
memset(tmp.mat,0,sizeof(tmp.mat));
for(int i=0;i<N;i++)
for(int k=0;k<N;k++)
if(mat[i][k])
for(int j=0;j<N;j++){
tmp.mat[i][j]+=(mat[i][k]*x.mat[k][j])%1000;
tmp.mat[i][j]%=1000;
}
return tmp;
}
}cat,b;
void _pow(int v){
memset(b.mat,0,sizeof(b.mat));
for(int i=0;i<n;i++)
b.mat[i][i]=1;
while(v){
if(v&1)
b=b*cat;
cat=cat*cat;
v>>=1;
}
}
int main(int argc, char** argv) {
int s,e,t,i,x,y,k;
node tmp;
while(scanf("%d%d",&n,&m)!=EOF&&n||m){
memset(cat.mat,0,sizeof(cat.mat));
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
cat.mat[x][y]=1;
}
tmp=cat;
scanf("%d",&t);
while(t--){
cat=tmp;
scanf("%d%d%d",&s,&e,&k);
_pow(k);
printf("%d\n",b.mat[s][e]);
}
}
return 0;
}