AT_abc399_g [ABC399G] Colorful Spanning Tree

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ M $ 辺の連結無向グラフが与えられます。グラフは自己ループを含みませんが、多重辺を含む可能性があります。辺には色がついていて、 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ色 $ c_i $ ( $ 1 \leq c_i \leq C $ ) の辺です。 また、数列 $ A = (A_1, A_2, \dots, A_C) $ が与えられます。 このグラフの全域木のうち次の条件を満たすものを **カラフル全域木** と呼びます。 - $ 1 \leq i \leq C $ を満たす全ての整数 $ i $ について、全域木に含まれる色 $ i $ の辺の本数は $ A_i $ 本以下である。 $ 1 \leq L \leq R \leq C $ を満たす整数の組 $ (L, R) $ のうち次の条件を満たすものの個数を求めてください。 - カラフル全域木 $ T $ であって、 $ T $ に含まれる任意の辺の色 $ c $ が $ L \leq c \leq R $ を満たすようなものが存在する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C $ $ A_1 $ $ A_2 $ $ \dots $ $ A_C $ $ u_1 $ $ v_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ \vdots $ $ u_M $ $ v_M $ $ c_M $

$ 1 \leq L \leq R \leq C $ を満たす整数の組 $ (L, R) $ のうち問題文の条件を満たすものの個数を出力せよ。

### Sample Explanation 1 例えば $ (L, R) = (1, 2) $ は問題文の条件を満たします。これは $ 1 $ 番目の辺と $ 4 $ 番目の辺からなる全域木 $ T $ はカラフル全域木で、かつ $ T $ に含まれる任意の辺の色が $ L $ 以上 $ R $ 以下であるからです。 問題文の条件を満たす $ (L, R) $ は $ (1, 2), (1, 3), (2, 2), (2, 3) $ の $ 4 $ 個です。 ### Constraints - $ 2 \leq N \leq 150 $ - $ N - 1 \leq M \leq \min\left(\frac{CN(N-1)}{2}, 5 \times 10^5\right) $ - $ 1 \leq C \leq 300 $ - $ 1 \leq A_i \leq N-1 $ - $ \sum_{i=1}^C A_i \leq 300 $ - $ 1 \leq u_i \lt v_i \leq N $ - $ 1 \leq c_i \leq C $ - $ i \neq j $ ならば $ (u_i,v_i,c_i) \neq (u_j,v_j,c_j) $ - 入力で与えられるグラフは連結 - 入力される値は全て整数