CF70E Information Reform

尽管现在已经是 21 世纪了，但是大众传播媒介在 Walrusland 依然没有普及开来。这里的城市通过能够在城市间的道路来往的信使来互相传递消息。在 Walrusland，城市间的道路保证信使可以从一座城市到任意另一座城市，而且这些道路是等长的。 北极政![]()府决定实施一项信息改革。几座城市被选中成为区域信息中心。维护一座区域信息中心每年需要花费 $k$ 个 fishlar（这是当地的货币）。假设每座区域信息中心总是能即时获得最新的消息。 每一座不是区域信息中心的城市，都会被安排通过一座区域信息中心来保持获取信息。这样，每年维护费用将会等于 $d_{len}$ 个 fishlar，其中 $len$ 表示这座城市到它的区域信息中心的距离，即一个人从这座城市到它的区域信息中心需要走过的道路条数。 你的任务是求出实行这项改革的最小开销。

第一行包含两个整数 $n$ 和 $k$（$1\le n\le 180,1\le k\le10^5$）。 第二行包含 $n-1$ 个整数 $d_i$，下标从 $1$ 开始（$d_i\le d_{i+1},0\le d_i\le10^5$）。 接下来的 $n-1$ 行包含被一条道路连接的城市对。

第一行输出每年维护信息联系的最小花销。第二行输出 $n$ 个整数，第 $i$ 个整数代表第 $i$ 座城市由编号为 $a_i$ 的区域信息中心负责通信；如果第 $i$ 座城市本身就是一座区域信息中心，你只需输出数字 $i$。 如果此题有多解，只需输出任意一组。

翻译 By @若如初见，修缮 By @[tallnut](https://www.luogu.com.cn/user/1037586)。