Problem Description

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?

Input Format

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$.

Output Format

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

4 3
1 2
2 3
3 4
0 3 3 3

5