#include<bits/stdc++.h>
using namespace std;

const int N = 2e2+10;
const int INF = 0x3f3f3f3f;

int n,m,k;
int f[N][N];

void Floyd(){
	for(int k = 1;k <= n; ++k)
		for(int i = 1;i <= n; ++i)
			for(int j = 1;j <= n; ++j)
				f[i][j] = min(f[i][j],f[i][k]+f[k][j]);
}

int main()
{
	cin>>n>>m>>k;
	int u,v,w;

	for(int i = 1;i <= n; ++i)
		for(int j = 1;j <= n; ++j)
			f[i][j] = i==j?0:INF;

	for(int i = 1;i <= m; ++i){
		cin>>u>>v>>w;
		f[u][v] = min(f[u][v],w);
	}
	Floyd();
	while(k--){
		cin>>u>>v;
		if(f[u][v] > INF / 2) cout<<"impossible"<<endl;
		else cout<<f[u][v]<<endl;
	}


	return 0;
}

直接Floyd 不会超时，每次枚举分割点就好了