当前没有测试数据。

G - Builder Takahashi

得分：$600$ 分

问题描述

我们有一个简单连通的无向图，有 $N$ 个顶点和 $M$ 条边。
顶点编号为 Vertex $1$，Vertex $2$，$\dots$，Vertex $N$。
边编号为 Edge $1$，Edge $2$，$\dots$，Edge $M$。第 $i$ 条边双向连接了 Vertex $a_i$ 和 Vertex $b_i$。没有直接连接 Vertex $1$ 和 Vertex $N$ 的边。
每个顶点要么为空，要么被一堵墙占据。最初，每个顶点都是空的。

Aoki 准备沿着图上的边从 Vertex $1$ 移动到 Vertex $N$。然而，Aoki 不被允许移动到一个被墙占据的顶点。

Takahashi 决定选择一些顶点来建墙，以便无论 Aoki 选取哪条路径，他都无法到达 Vertex $N$。
在顶点 $i$ 处建墙对 Takahashi 的开销为 $c_i$ 日元（日本货币）。他不可以在顶点 $1$ 和顶点 $N$ 处建墙。

Takahashi 需要支付多少日元来建造这些阻止 Aoki 进入 Vertex $N$ 的墙？并且输出建墙的最小成本的方式。

约束

• $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$
• 输入中的所有值都是整数。

---

输入

从标准输入中按照以下格式输入：

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_M$ $b_M$

$c_1$ $c_2$ $\dots$ $c_N$

输出

按照以下格式输出。这里的 $C$，$k$，$p_i$ 的定义如下。

• $C$ 是 Takahashi 需要支付的费用
• $k$ 是 Takahashi 需要建墙的顶点数
• $(p_1,p_2,\dots,p_k)$ 是 Takahashi 将要建墙的顶点的序列

``` $C$ $k$ $p_1$ $p_2$ $\dots$ $p_k$ ```

如果有多种建造墙壁的方式同时满足要求的最小成本，可以输出任意一种。

---

5 5
1 2
2 3
3 5
2 4
4 5
0 8 3 4 0

7
2
3 4

如果 Takahashi 在 Vertex $3$ 和 Vertex $4$ 处建墙，每个顶点分别花费 $3$ 和 $4$ 日元，Aoki 将无法从 Vertex $1$ 到达 Vertex $5$。
没有比这更小成本的方式满足要求，所以答案是 $7$ 日元。

---

3 2
1 2
2 3
0 1 0

1
1
2

---

5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
0 1000000000 1000000000 1000000000 0

3000000000
3
2 3 4