AT_abc239_g [ABC239G] Builder Takahashi

给定一张 $n$ 个点 $m$ 条边的连通无向图，要求在某些点（不能为 $1$ 号点或者 $n$ 号点）设立障碍，在 $i$ 号点建立障碍的费用为 $c_i$，要使得 $1$ 号点和 $n$ 号点不连通，求最小花费的方案。

第一行两个整数 $n,m(3\leq n\leq 100,n−1\leq m\leq \frac{n(n−1)}{2}−1)$。 接下来 $m$ 行，每行两个数 $a_i,b_i(1\leq ai < bi\leq n)$，保证没有重边自环，并且 $1$ 与 $n$ 不直接相连。 接下来一行 $n$ 个整数 $c_1,c_2,…,c_n(0\le ci\le 10^9)$，保证 $c_1=c_n=0$。

第一行输出一个数，表示最小的花费。 接下来输出一个数 $k$，表示建立障碍的个数。接下来一行 $k$ 个数，表示建立障碍的 $k$ 个点。

### 制約 - $ 3\ \leq\ N\ \leq\ 100 $ - $ N\ -\ 1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}\ -\ 1 $ - $ 1\ \leq\ a_i\ \lt\ b_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ (a_i,\ b_i)\ \neq\ (1,\ N) $ - 与えられるグラフは単純かつ連結である。 - $ 1\ \leq\ c_{i}\ \leq\ 10^9 $ $ (2\ \leq\ i\ \leq\ N-1) $ - $ c_1\ =\ c_N\ =\ 0 $ - 入力はすべて整数である。 ### Sample Explanation 1 高橋君が $ 3\ +\ 4\ =\ 7 $ 円を払って頂点 $ 3 $, 頂点 $ 4 $ に壁を建てると青木君は頂点 $ 1 $ から頂点 $ 5 $ へ行くことができなくなります。 これより少ない金額で条件を満たすことはできないので $ 7 $ 円が答えとなります。