配点 : $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$

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

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

7
2
3 4

高橋君が $3 + 4 = 7$ 円を払って頂点 $3$, 頂点 $4$ に壁を建てると青木君は頂点 $1$ から頂点 $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