题目描述

$\red{FJ}$决定搬家，重新建设农场，以便最小化他每天的行程。

$\red{FJ}$搬往的区域有$\red{N(1 <= N <= 10,000)}$个城镇，共有$\red{M (1 <= M <= 50,000)}$条双向道路连接某些城镇，所有城镇都能找到互通路线。

有$\red{K (1 <= K <= 5)}$个城镇建有市场，$\red{FJ}$每天离开新农场后，都要光顾这$\red{K}$个城镇，并返回农场。$\red{FJ}$希望建设农场的城镇不包含市场。

请帮助$\red{FJ}$选择最佳城镇建设农场，使得他每天的行程最小。

输入格式

第 $\red{1 }$行：三个以空格分隔的整数 $\red{N}$、$\red{M }$和 $\red{K}$。

第 $\red{2..1+K }$行：第 $\red{i+1 }$行包含 $\red{1...N }$范围内的整数，用于标识包含第 $\red{i }$个市场的城镇。每个市场位于不同的城镇。

第 $\red{2+K..1+K+M }$行：每行包含 $\red{3 }$个空格分隔的整数，$\red{i,j (1 <= i,j <= N) }$和 $\red{L (1 <= L <= 1000)，}$表示从城镇 $\red{i }$到城镇 $\red{j }$存在一条长度为 $\red{L }$的道路。

输出格式

第 $\red{1 }$行：如果 $\red{FJ }$在最佳位置建造农场，他在日常工作中需要走的最短距离。

样例

输入样例

5 6 3 
1 
2 
3 
1 2 1 
1 5 2 
3 2 3 
3 4 5 
4 2 7 
4 5 10

输出样例

12

提示

有$\red{5}$个镇，$\red{1}$、$\red{2}$、$\red{3}$镇有市场。有$\red{6}$条道路。

$\red{FJ }$在 $\red{5 }$号镇建立了他的农场。他每天的日程安排带他穿过 $\red{5-1-2-3-2-1-5 }$镇，总距离为 $\red{12}$。