G - Builder Takahashi 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の単純連結無向グラフがあります。
頂点には頂点 1, 頂点 2, \dots, 頂点 N と番号が振られています。
辺には 辺 1, 辺 2, \dots, 辺 M と番号が振られています。辺 i は頂点 a_i と頂点 b_i を双方向に結んでいます。また、頂点 1 と頂点 N を直接結ぶ辺は存在しません。
各頂点の状態は「何もない頂点」か「壁がある頂点」のいずれかです。はじめ、全ての頂点は何もない頂点です。

青木君は頂点 1 を出発して、グラフ上を辺に沿って移動して頂点 N へ行こうとしています。ただし、壁がある頂点への移動を行うことはできません。

高橋君は、青木君が移動を開始する前にいくつかの頂点を選んで壁を建てることで、青木君がどのように移動しても頂点 N へ行くことができないようにすることにしました。
高橋君が頂点 i に壁を建てるには c_i 円を払う必要があります。また、頂点 1 および頂点 N には壁を建てられません。

高橋君が条件を満たすように壁を建てるときに最小で何円払う必要があるでしょうか。また、その時の壁の立て方を 1 つ出力してください。

制約

  • 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 は高橋君が支払う金額
  • k は高橋君が壁を建てる頂点の個数
  • (p_1,p_2,\dots,p_k) は高橋君が壁を建てる頂点からなる列
C
k
p_1 p_2 \dots p_k

最小の金額で条件を満たす建て方が複数存在する場合はどれを出力してもよい。

入力例 1

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

出力例 1

7
2
3 4

高橋君が 3 + 4 = 7 円を払って頂点 3, 頂点 4 に壁を建てると青木君は頂点 1 から頂点 5 へ行くことができなくなります。
これより少ない金額で条件を満たすことはできないので 7 円が答えとなります。

入力例 2

3 2
1 2
2 3
0 1 0

出力例 2

1
1
2

入力例 3

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

出力例 3

3000000000
3
2 3 4

Score : 600 points

Problem Statement

We have a simple connected undirected graph with N vertices and M edges.
The vertices are numbered as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are numbered as Edge 1, Edge 2, \dots, Edge M. Edge i connects Vertex a_i and Vertex b_i bidirectionally. There is no edge that directly connects Vertex 1 and Vertex N.
Each vertex is either empty or occupied by a wall. Initially, every vertex is empty.

Aoki is going to travel from Vertex 1 to Vertex N along the edges on the graph. However, Aoki is not allowed to move to a vertex occupied by a wall.

Takahashi has decided to choose some of the vertices to build walls on, so that Aoki cannot travel to Vertex N no matter which route he takes.
Building a wall on Vertex i costs Takahashi c_i yen (the currency of Japan). He cannot build a wall on Vertex 1 and Vertex N.

How many yens is required for Takahashi to build walls so that the conditions is satisfied? Also, print the way of building walls to achieve the minimum cost.

Constraints

  • 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)
  • The given graph is simple and connected.
  • 1 \leq c_{i} \leq 10^9 (2 \leq i \leq N-1)
  • c_1 = c_N = 0
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M
c_1 c_2 \dots c_N

Output

Print in the following format. Here, C,k, and p_i are defined as follows.

  • C is the cost that Takahashi will pay
  • k is the number of vertices for Takahashi to build walls on
  • (p_1,p_2,\dots,p_k) is a sequence of vertices on which Takahashi will build walls
C
k
p_1 p_2 \dots p_k

If there are multiple ways to build walls to satisfy the conditions with the minimum cost, print any of them.

Sample Input 1

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

Sample Output 1

7
2
3 4

If Takahashi builds walls on Vertex 3 and Vertex 4, paying 3 + 4 = 7 yen, Aoki is unable to travel from Vertex 1 to Vertex 5.
There is no way to satisfy the condition with less cost, so 7 yen is the answer.

Sample Input 2

3 2
1 2
2 3
0 1 0

Sample Output 2

1
1
2

Sample Input 3

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

Sample Output 3

3000000000
3
2 3 4