[cpp]
//ZOJ 3396 Conference Call
//题意 求经过特定3点的最小生成树
//思路：枚举任何一点作为支撑点 ,特定的3点要相连必须经过共同的一点 ,求这三点到所枚举点的最短路和，取最小值即为答案
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define INF 50000000
#define N 20005
#define M 505
int n, m, k;
int sta[N];
int head[M], num;
int dis[4][M];
bool vis[M], mark[M];
struct Edge {
int from;
int to;
int val;
int next;
} edge[N];
void addedge（int from, int to, int val） {
edge[num].from = from;
edge[num].to = to;
edge[num].val = val;
edge[num].next = head[from];
head[from] = num++;
}
void init（） {
memset（head, -1, sizeof （head））；
num = 0;
}
void spfa（int s, int index） {
memset（vis, 0, sizeof （vis））；
for （int i = 1; i <= m; ++i）
dis[index][i] = INF;
queue<int> Q;
Q.push（s）；
dis[index][s] = 0;
vis[s] = 1;
while （！Q.empty（）） {
int p = Q.front（）；
Q.pop（）；
vis[p] = 0;
for （int i = head[p]; i != -1; i = edge[i].next） {
if （dis[index][edge[i].to] > dis[index][p] + edge[i].val） {
dis[index][edge[i].to] = dis[index][p] + edge[i].val;
if （！vis[edge[i].to]） {
Q.push（edge[i].to）；
vis[edge[i].to] = 1;
}
}
}
}
}
int main（） {
int i, j, ca = 1;
int a, b, c;
while （scanf（"%d %d %d", &n, &m, &k） != EOF） {
init（）；
for （i = 1; i <= n; ++i）
scanf（"%d", &sta[i]）；
for （i = 1; i <= k; ++i） {
scanf（"%d %d %d", &a, &b, &c）；
addedge（a, b, c）；
addedge（b, a, c）；
}
int bx;
int qua;
scanf（"%d", &qua）；
printf（"Case #%d\n", ca++）；
for （i = 1; i <= qua; ++i） {
scanf（"%d %d %d", &a, &b, &c）；
spfa（sta[a], 1）；
spfa（sta[b], 2）；
spfa（sta[c], 3）；
int ans = INF;
for （j = 1; j <= m; ++j）
if （dis[1][j] + dis[2][j] + dis[3][j] < ans）{
ans = dis[1][j] + dis[2][j] + dis[3][j];
bx = j;
}
printf（"Line %d: ", i）；
// printf（"bx :%d %d %d %d\n",bx,dis[1][bx],dis[2][bx],dis[3][bx]）；
if （ans == INF）
printf（"Impossible to connect!\n"）；
else
printf（"The minimum cost for this line is %d.\n", ans）；
}
}
return 0;
}