题目描述

众所周知，Naomi 的数学不太好。但 Naomi 每天都在练习数学题。以下是其中一道。

Naomi 有一个包含 $n$ 个顶点（编号从 $1$ 到 $n$）和 $m$ 条边的无向连通图。每条边的长度均为 $1$。Naomi 需要向图中添加一些边（长度同样应为 $1$），每条新边连接两个不同的顶点，并使得图的代价最小。

定义 $\text{dist}[i]$ 为顶点 $1$ 到顶点 $i$ 的最短路径长度。顶点 $i$ 有一个权值 $A[i]$。图的代价等于 $\sum_{i=1}^n (A[i] - \text{dist}[i])^2$。

你能帮帮她吗？

输入格式

输入包含多组测试数据。（不超过 $20$ 组）

对于每组测试数据：

第一行包含两个整数 $n$、$m$。（$1 \le n \le 40$，$0 \le m \le 1600$）

接下来的 $m$ 行，每行包含两个整数 $x$、$y$（$1 \le x, y \le n$），表示 $x$ 与 $y$ 之间有一条边。

每组数据的最后一行包含 $n$ 个整数，表示数组 $A$。$0 \le A[i] \le 1000$。

输出格式

对于每组测试数据，在一行中输出图的最小代价。

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

5

提示

翻译由 DeepSeek V4 Pro 完成