#include <bits/stdc++.h>
using namespace std;const int N=0x3fffffff;int a[201][201],x,y,z,k,n,m;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for (int i=1;i<=n;++i){for (int j=1;j<=n;++j){if (i==j){a[i][j]=0;}else{a[i][j]=N;}}}for (int i=1;i<=m;++i){cin>>x>>y>>z;a[x][y]=z;}for (int k=1;k<=n;++k){for (int i=1;i<=n;++i){for (int j=1;j<=n;++j){if (a[i][j]>a[i][k]+a[k][j]){a[i][j]=a[i][k]+a[k][j];}}}}cin>>k;while (k--){cin>>x>>y;if(a[x][y]>N/2){cout<<"impossible"<<endl;}else{cout<<a[x][y]<<endl;}}return 0;}