floyd求最短路

//floyd求最短路 
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=210,INF=1e9;
int d[N][N],n,m,q;

void floyd()      //基于动态规划实现，背过 
{
	for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	        for(int j=1;j<=n;j++)
	        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main(void)
{
	cin>>n>>m>>q;
	
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
   		    if(i==j)d[i][j]=0;   //因为存在自环，因此初始化为0，保证自环全为0 
   		    else d[i][j]=INF; 
   		    
    while(m--)
    {
    	int a,b,x;
    	cin>>a>>b>>x;
    	d[a][b]=min(d[a][b],x);	//存在重边，保留最小边 
	}
	floyd();
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(d[a][b]>INF/2)puts("impossible");
		else cout<<d[a][b]<<endl;
	}
	return 0;
 }