#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#include <queue>#include <cmath>#include <string>#include <string.h>#include <iterator>#include <cstdlib>#include<stack>#include<map>#include<set>#define inff 0x1f#define EPS 1e-7#define maxm 200000000#define MAXN 33#define inf 1000000000#define L(x) (x<<1)#define R(x) (x<<1|1)#define N 1002#define mod 2008#define pi 3.1415926535using namespace std;queue<int>q;struct node{ int v,c,next;}ed[20006];int dis[502][502],n,m,p[502],id,flag[100002],ff[502];int spfa(int v,int dis[]){int i,f[502],cnt[502],k;for (i=1;i<=n;i++){dis[i]=inf;f[i]=0;cnt[i]=0;}dis[v]=0;f[v]=1;cnt[v]++;while(!q.empty())q.pop(); q.push(v);while(!q.empty()){k=q.front();q.pop();f[k]=0;for (i=p[k];i!=-1;i=ed[i].next){if (dis[ed[i].v]>dis[k]+ed[i].c){dis[ed[i].v]=dis[k]+ed[i].c;if (!f[ed[i].v]){f[ed[i].v]=1;cnt[ed[i].v]++;q.push(ed[i].v);if(cnt[ed[i].v]>=n) return 1;}}}}return 0;}int main() { int i,s,e,l;int ca=1;while(scanf("%d%d%d",&m,&n,&l)!=EOF){memset(p,-1,sizeof(p)); memset(ff,0,sizeof(ff)); for(i=1;i<=m;i++){ scanf("%d",&flag[i]);}id=0;for (i=0;i<l;i++){int w;scanf("%d%d%d",&s,&e,&w);ed[id].next=p[s];ed[id].v=e;ed[id].c=w;p[s]=id;id++;ed[id].next=p[e];ed[id].v=s;ed[id].c=w;p[e]=id;id++;} int qi; scanf("%d",&qi);printf("Case #%dn",ca++);int qq=1;while(qi--){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(ff[flag[x]]==0){spfa(flag[x],dis[flag[x]]);ff[flag[x]]=1;}if(ff[flag[y]]==0){spfa(flag[y],dis[flag[y]]);ff[flag[y]]=1;}if(ff[flag[z]]==0){spfa(flag[z],dis[flag[z]]);ff[flag[z]]=1;}int ans=inf;for (i=1;i<=n;i++){if(dis[flag[x]][i]==inf||dis[flag[y]][i]==inf||dis[flag[z]][i]==inf) continue;int ss=dis[flag[x]][i]+dis[flag[y]][i]+dis[flag[z]][i];if(ss<ans) ans=ss;}if(ans==inf) printf("Line %d: Impossible to connect!n",qq++);elseprintf("Line %d: The minimum cost for this line is %d.n",qq++,ans);}} return 0;}
