POJ3114

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <csignal>
#include <csetjmp>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
bool ins[550],vis[550],vis1[550];
int dfn[550],low[550],bel[550],dis[550];
int t,bcnt,top,n,m;
int s[550];
struct node{
	int v,w;
};
vector<node> g[550],G[550];
inline void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x<10){
		putchar(x^48);
		return;
	}
	print(x/10);
	putchar(x%10^48);
}
void dij(int x,int y){
	memset(dis,0x3f,sizeof(dis));
	dis[x]=0;
	priority_queue < pair<int,int> > q;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis1[u])continue;
		vis1[u]=true;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			int w=G[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	} 
	if(dis[y]!=0x3f3f3f3f)print(dis[y]),putchar('\n');
	else puts("Nao e possivel entregar a carta");
}
void tarjan(int u){
	int v;
	low[u]=dfn[u]=++t;
	s[top++]=u;
	ins[u]=true;
	for(int i=0;i<g[u].size();i++){
		v=g[u][i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(ins[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		bcnt++;
		do{
			v=s[--top];
			ins[v]=false;
			bel[v]=bcnt;
		}while(v!=u);
	}
}

inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-'){
		k=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*k;
}

int main(){
	int u,v,a,b,w;
	while(cin>>n>>m && (n || m)){
		t=bcnt=top=0;
		for(int i=1;i<=n;i++)G[i].clear(),g[i].clear();
		memset(ins,false,sizeof(ins));
		memset(dfn,0,sizeof(dfn));
		memset(dis,0x3f,sizeof(dis));
		while(m--){
			a=read();
			b=read();
			w=read();
			g[a].push_back({b,w});
		}
		for(u=1;u<=n;u++){
			if(!dfn[u])tarjan(u);
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<g[i].size();j++){
				int v=g[i][j].v,w=g[i][j].w;
				if(bel[i]!=bel[v])G[bel[i]].push_back({bel[v],w});
			}
		}
		int q;
		cin>>q;
		while(q--){
			int a,b;
			a=read(),b=read();
			dij(bel[a],bel[b]);
		}
		putchar('\n');	
	}
}