22416번 - Escape 다국어

頂点に正の値を持つ無向グラフが与えられる。 頂点には 1 から $N$ の番号がついており、$i$ 番目の頂点は $w_i$ の値を持っている。 1 番目の頂点からスタートし、直前に通った辺を通ることができないという制約のもとでグラフ上を移動することができる。 各頂点では，初めて訪れた時に限りその頂点が持つ値の点数を得られる。

取得できる点数の総和の最大値を求めよ。

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$w_1$ $w_2$ $...$ $w_N$

$u_1$ $v_1$

$u_2$ $v_2$

$...$

$u_M$ $v_M$

$1$ 行目にはグラフの頂点数 $N$ と辺の数を表す整数 $M$ が入力される。$2$ 行目には各頂点が持つ値 $w_i$ が入力される。さらに続けて $M$ 行に、各辺により繋がれる $2$ 頂点の番号が入力される。

答えを1行に出力せよ。

• $1 \leq N \leq 100000$
• $N-1 \leq M \leq 100000$
• $1 \leq w_i \leq 1000$
• $1 \leq u_i, v_i \leq N$
• 多重辺・自己辺は存在しない
• グラフは連結である