1110. 最长路

#include<bits/stdc++.h>
#define FUCK ios::sync_with_stdio(false);
using namespace std;
int main()
{
    FUCK;cin.tie(0);
    int n,m;
    while(cin>>n>>m){
        int grath[n+1][n+1]={0},dp[n+1][n+1]={0};
        int i,j,k;
        for(k=0;k<m;k++){
            int u,v,w;cin>>u>>v>>w;
            grath[u][v]=w;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(i!=j){
                    int MIN=-100000;
                    for(k=1;k<=n;k++){
                        if(grath[k][j]!=0&&grath[k][j]+dp[i][k]>MIN){
                            MIN=grath[k][j]+dp[i][k];
                        }
                    }
                    dp[i][j]=MIN;
                }
                else if(i==j) dp[i][j]=0;
            }
        }
        int p;cin>>p;
        while(p--){
            int u,v;cin>>u>>v;
            if(dp[u][v]<0) cout<<-1<<endl;
            else cout<<dp[u][v]<<endl;
        }
    }
}