Description

Farmer John is moving and wants to build a new farm so that his daily travel distance is minimized.

The region has $N$ towns ($1 \le N \le 10{,}000$). There are $M$ bidirectional roads ($1 \le M \le 50{,}000$) connecting certain pairs of towns, and every town is reachable from every other town by some combination of roads. There are markets in $K$ towns ($1 \le K \le 5$) that FJ wants to visit every day. Each day, he will leave his new farm, visit all $K$ market towns in any order he chooses, and then return to his farm.

When choosing a town for his new farm, FJ will only consider the $N - K$ towns that do not have markets, since housing prices are lower in those towns.

Please compute the minimum total distance FJ needs to travel in his daily routine if he builds his farm in an optimal town and plans his route to the markets optimally.

Input Format

• Line 1: Three space-separated integers $N$, $M$, and $K$.
• Lines $2 \ldots 1+K$: Line $i+1$ contains an integer in the range $1 \ldots N$ identifying the town containing the $i$-th market. Each market is in a different town.
• Lines $2+K \ldots 1+K+M$: Each line contains three space-separated integers $i$, $j$ ($1 \le i, j \le N$), and $L$ ($1 \le L \le 1000$), indicating a bidirectional road of length $L$ between towns $i$ and $j$.

Output Format

• Line 1: The minimum distance FJ needs to travel during his daily routine, if he builds his farm in an optimal location.

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 

Hint

There are $5$ towns, with towns $1$, $2$, and $3$ having markets. There are $6$ roads. FJ builds his farm in town $5$. His daily route is $5$-$1$-$2$-$3$-$2$-$1$-$5$, for a total distance of $12$.

Translated by ChatGPT 5