1 #include <cstdio>  2 #include <cstring>  3 #include <iostream>  4 #include <vector>  5 #include <stack>  6 #include <queue>  7 #include <algorithm>  8 #define maxn 505  9 using namespace std ; 10  11 struct node 12 { 13     int u,v,w,next ; 14 } edge[maxn*maxn]; 15 int p[maxn][maxn]; 16 int dfn[maxn],low[maxn],head[maxn] ,vis[maxn],dis[maxn],belong[maxn]; 17 int timee,cnt ,cntt,n,m; 18 stack<int>stk ; 19  20 void Init() 21 { 22     timee = 0 ; 23     cnt = cntt = 0 ; 24     memset(dfn,0,sizeof(dfn)) ; 25     memset(low,0,sizeof(low)) ; 26     memset(dis,0,sizeof(dis)) ; 27     memset(head,-1,sizeof(head)) ; 28     memset(vis,0,sizeof(vis)) ; 29     memset(p,0x3f,sizeof(p)) ; 30 } 31 void addedge(int u,int v,int w) 32 { 33     edge[cnt].u = u ; 34     edge[cnt].v = v ; 35     edge[cnt].w = w ; 36     edge[cnt].next = head[u] ; 37     head[u] = cnt++ ; 38 } 39 void tarjan(int u) 40 { 41     //cout<<u<<endl; 42     int v ; 43     vis[u] = 1 ; 44     dfn[u] = low[u] = ++ timee ; 45     stk.push(u) ; 46     for(int i = head[u] ; i != -1 ; i = edge[i].next) 47     { 48         v = edge[i].v ; 49         if(!dfn[v]) 50         { 51             //printf("v = %d\n",v) ; 52             tarjan(v) ; 53             low[u] = min(low[v],low[u]) ; 54         } 55         else if(vis[v]) 56             low[u] = min(low[u],dfn[v]) ; 57     } 58     if(low[u] == dfn[u]) 59     { 60         cntt ++ ; 61         do 62         { 63             v = stk.top() ; 64             stk.pop() ; 65             vis[v] = 0 ; 66             belong [v] = cntt ; 67          //   puts("1") ; 68         } 69         while(v != u) ; 70     } 71 } 72 void SPFA(int u,int v) 73 { 74     queue<int>Q ; 75     for(int i = 1 ; i <= cntt ; i++) 76     { 77         dis[i] = 999999999 ; 78         vis[i] = 0 ; 79     } 80     dis[u] = 0; 81     vis[u] = 1; 82     Q.push(u) ; 83     while(!Q.empty()) 84     { 85         int s = Q.front() ; 86         Q.pop() ; 87         vis[s] = 0 ; 88         for(int i = 1 ; i <= n ; i ++ ) 89         { 90             if(p[s][i] != 999999999) 91             { 92                 if(dis[i] > dis[s] + p[s][i]) 93                 { 94                     dis[i] = dis[s] + p[s][i] ; 95                     if(!vis[i]) 96                     { 97                         Q.push(i) ; 98                         vis[i] = 1 ; 99                     }100                 }101             }102         }103     }104     if(dis[v] != 999999999)105         printf("%d\n",dis[v]) ;106     else printf("Nao e possivel entregar a carta\n") ;107 }108 void rebuild()109 {110     for(int i = 1 ; i <= n ; i++)111     {112         for(int j = head[i] ; j != -1 ; j = edge[j].next)113         {114          //   int s = edge[i].v ;115             int v = belong[edge[j].v] ;116             int u = belong[edge[j].u] ;117             if(u != v)118                 p[u][v] = min(p[u][v],edge[j].w) ;119         }120     }121     for(int i = 1 ; i <= cntt ; i++)122         p[i][i] = 0 ;123 }124 int main()125 {126     int x,y,h,k;127     while(~scanf("%d %d",&n,&m))128     {129         if(n == 0 && m == 0) break ;130         Init() ;131         for(int i = 0 ; i < m ; i++)132         {133             scanf("%d %d %d",&x,&y,&h) ;134             addedge(x,y,h) ;135         }136         for(int i = 1 ; i <= n ; i++)137         {138             if(!dfn[i])139                 tarjan(i) ;140         }141        // cout<<"s"<<endl;142         rebuild() ;143        // cout<<"s"<<endl;144         scanf("%d",&k) ;145         for(int i = 0 ; i < k ; i++)146         {147             //cout<<i<<endl;148             scanf("%d %d",&x,&y) ;149             SPFA(belong[x],belong[y]) ;150         }151         printf("\n") ;152     }153     return 0 ;154 }