AT_cpsco2019_s2_g MSTX

[problemUrl]: https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_g $ N $ 頂点 $ M $ 辺の単純無向連結グラフが与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と $ v_i $ を結んでいて、重みは $ w_i $ です。 $ w_i $は正整数の定数、もしくは変数 $ x $ です。 以下の $ Q $ 個のクエリをすべて処理してください。 - $ i $ 番目のクエリでは、正整数 $ a_i $ が与えられる。 - $ x=a_i $ としたときの最小全域木の重みを求めよ。

入力は以下の形式で標準入力から与えられる。 ただし、 $ c_i $ は文字 `0` または `1` であり、これは $ w_i $ が定数か変数かを表している。 $ c_i $ が `0` のとき、 $ w_i $ は正整数の定数であり、 $ c_i $ が `1` のとき、 $ w_i $ は文字 `x` である。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ c_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ w_2 $ $ : $ $ u_M $ $ v_M $ $ c_M $ $ w_M $ $ Q $ $ a_1 $ $ a_2 $ $ : $ $ a_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリの答えを出力せよ。

### 制約 - $ 2\ \le\ N\ \le\ 5\ \times\ 10^4 $ - $ N-1\ \le\ M\ \le\ min(5\ \times\ 10^4,\ N(N-1)/2) $ - $ 1\ \le\ u_i,v_i\ \le\ N $ - $ u_i\ \neq\ v_i $ - $ i\ \neq\ j $ のとき $ (u_i,v_i)\ \neq\ (u_j,v_j) $ かつ $ (u_i,v_i)\ \neq\ (v_j,u_j) $ - 与えられるグラフは連結である。 - $ w_i $ が定数のとき、$ 1\ \le\ w_i\ \le\ 10^9 $ - $ 1\ \le\ Q\ \le\ 5\ \times\ 10^4 $ - $ 1\ \le\ a_i\ \le\ 10^9 $ - 入力は、文字 `x` を除けば、すべて整数である。 ### Sample Explanation 1 このケースでは、 - $ x\ \le\ 5 $ のとき最小全域木の重みは $ x+1 $ - $ x\ \ge\ 5 $ のとき最小全域木の重みは $ 6 $ となります。