AT_pakencamp_2021_day2_g 進撃のパ研

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day2/tasks/pakencamp_2021_day2_g パ研部長のぺんぎんくんは、パ研の部室を増やしたいと思いました。 ぺんぎんくんのいる学校には $ N $ 個の部屋があり、部屋 $ 1 $ から部屋 $ N $ までの番号が付けられています。 また、$ M $ 本の廊下があり、$ i $ 番目の廊下は部屋 $ U_i $ と部屋 $ V_i $ を双方向に結んでいます。これらの廊下を使って移動することで、どの部屋からどの部屋にも行くことができます。 現在、パ研の部室は部屋 $ 1 $ のみです。ぺんぎんくんは今日を $ 1 $ 日目として、 $ 1 $ 日 $ 1 $ 回以下の操作を行うことで、$ N-1 $ 日目に全ての部屋がパ研の部室となっているようにします。 - 現時点でパ研の部室である部屋のいずれかと直接廊下で結ばれていてかつ現時点ではパ研の部室ではない部屋を $ 1 $ つ選び、新しくパ研の部室とする。 $ i $ 日目に部屋 $ j $ を新しくパ研の部室にしたとき、ぺんぎんくんの*嬉しさ*は $ A_{i,j} $ 上昇します。はじめ、ぺんぎんくんの嬉しさは $ 0 $ です。 $ N-1 $ 日目の操作が終わった時点でのぺんぎんくんの嬉しさとして考えられる値の最大値を求め、出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ \vdots $ $ U_M $ $ V_M $ $ A_{1,1} $ $ A_{1,2} $ $ \cdots $ $ A_{1,N} $ $ \vdots $ $ A_{N-1,1} $ $ A_{N-1,2} $ $ \cdots $ $ A_{N-1,N} $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 15 $ - $ 1\ \leq\ M\ \leq\ \frac{N(N-1)}{2} $ - $ 1\ \leq\ U_i\