Contest Duration: - (local time) (100 minutes) Back to Home
G - Builder Takahashi /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 頂点 M 辺の単純連結無向グラフがあります。

### 制約

• 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_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


これより少ない金額で条件を満たすことはできないので 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