#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int n,m,k,tot=0,color=0;
int dfn[510],low[510],colour[510],map[510][510],neww[510][510];
vector<int>g[510];
stack<int>s;
int head,tail;
int que[510],vist[510],dist[510];
int min(int x,int y)
{
	if(x>y) return y;
	  return x;
}
void dfs(int x)
{
	int u,v,i;
	tot++;
	dfn[x]=tot;
	low[x]=tot;
	s.push(x);
	for(i=0;i<g[x].size();i++)
	{
		u=g[x][i];
		if(dfn[u]==0)
		{
			dfs(u);
			low[x]=min(low[x],low[u]);
		}
		 else if(colour[u]==0)
		   low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]) {
	 color++;
	 while(true)
	 {
		v=s.top();
		s.pop();
		colour[v]=color;
		if(x==v) break;
	 }
     }
}
int  spfa(int x,int goal)
{
	int u,v,i;
	u=que[1]=colour[x];
	vist[que[1]]=1;
	goal=colour[goal];
	dist[u]=0;
	while(head<tail)
	{
		head++;
		u=que[head];
		for(i=1;i<=color;i++)
		  if(neww[u][i]!=0&&dist[i]>dist[u]+neww[u][i])
		  {
		  	dist[i]=dist[u]+neww[u][i];
		  	if(vist[i]==0)
		  	{
		  		tail++;
				que[tail]=i;
				vist[i]=1;
			}
		  }
	    vist[u]=0;	
	}
	return dist[goal];
}
void initt()
{
	memset(vist,0,sizeof(vist));
	memset(que,0,sizeof(que));
	memset(dist,127,sizeof(dist));
	head=0;tail=1;
}
void init()
{
	int i;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(colour,0,sizeof(colour));
	for(i=0;i<n;i++)
	 g[i].clear();
	 tot=0; color=0;
}
int main()
{
	freopen("poj3114.in","r",stdin);
	freopen("poj3114.out","w",stdout);
	
	int i,j,x,y,h,u;
	while(true)
	{
		scanf("%d",&n);
		if(n==0) break;
		scanf("%d",&m); 
		init();
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&h);
			g[x].push_back(y);
			map[x][y]=h;
		}
		for(i=1;i<=n;i++)
		   if(dfn[i]==0)
		    dfs(i);
		for(i=1;i<=n;i++)
		  for(j=0;j<g[i].size();j++)
		  {
		  	  u=g[i][j];
			  if(colour[i]!=colour[u]){
			  	if(neww[colour[i]][colour[u]]==0)
			  	   neww[colour[i]][colour[u]]=map[i][u];
			  	 else neww[colour[i]][colour[u]]=min(neww[colour[i]][colour[u]],map[i][u]);			  
	           }
		  }
	   int ans=0;
	   scanf("%d",&k);
	   while(k>0)
	   {
	   	 initt();
		 k--;
	   	 scanf("%d%d",&x,&y);
	   	ans=spfa(x,y); 
	   	if(ans==2139062143) printf("Nao e possivel entregar a carta\n");
		   else printf("%d\n",ans);
	   }
	   printf("\n");
	}
	return 0;
}