P17150 [ICPC 2017 Xi'an R] Naomi with Graph

As we know, Naomi is poor at math. But Naomi practices math problems every day. The following is one of them. Naomi has a non-directed connected graph with $n$ vertices labelled from $1$ to $n$ and $m$ edges. The length of each edge is $1$. Naomi needs to add some edges (lengths of which should be $1$ as well) to the graph such that each of them connects two different vertices and minimize the cost of the graph. We define $\text{dist}[i]$ as the length of the shortest path between vertex $1$ and vertex $i$. Vertex $i$ has a value $A[i]$. The cost of the graph equals to $\sum_{i=1}^n (A[i] - \text{dist}[i])^2$. Can you help her?

The input contains multiple test cases. (No more than $20$) In each test case: The first line contains two numbers $n$, $m$. ($1 \le n \le 40,\ 0 \le m \le 1600$) The following $m$ lines each contain two numbers $x$, $y$ ($1 \le x, y \le n$) denoting that there is an edge between $x$ and $y$. And the last line of each test case contains $n$ numbers denoting the array $A$. $0 \le A[i] \le 1000$.

For each test case, print the minimum cost of the graph in a single line.