题目描述

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

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

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

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

输入格式

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

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

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

输出格式

第 ${1 }$行：如果 ${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

提示

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

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