AT_abc399_g [ABC399G] Colorful Spanning Tree

You are given a connected undirected graph with $ N $ vertices and $ M $ edges, where the vertices are labeled $ 1 $ to $ N $ . The graph does not contain self-loops, but it may contain multi-edges. Each edge has a color, and the $ i $ -th edge has a color $ c_i $ ( $ 1 \leq c_i \leq C $ ) and connects vertices $ u_i $ and $ v_i $ . Also, a sequence $ A = (A_1, A_2, \dots, A_C) $ is given. Among the spanning trees of this graph, those satisfying the following condition are called **colorful spanning trees**: - For every integer $ i $ such that $ 1 \leq i \leq C $ , the number of edges of color $ i $ included in the spanning tree is at most $ A_i $ . Find the number of integer pairs $ (L, R) $ with $ 1 \leq L \leq R \leq C $ that satisfy the following condition: - There exists a colorful spanning tree $ T $ such that every edge in $ T $ has a color $ c $ with $ L \leq c \leq R $ .

The input is given from Standard Input in the following format: > $ 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 $

Print the number of integer pairs $ (L, R) $ with $ 1 \leq L \leq R \leq C $ that satisfy the condition in the problem statement.

### Sample Explanation 1 For example, $ (L, R) = (1, 2) $ satisfies the condition, because the spanning tree $ T $ formed by the 1st and 4th edges is a colorful spanning tree, and all edges in $ T $ have colors $ c $ with $ 1 \leq c \leq 2 $ . There are four pairs $ (L, R) $ that satisfy the condition: $ (1, 2), (1, 3), (2, 2), (2, 3) $ . ### Constraints - $ 2 \leq N \leq 150 $ - $ N - 1 \leq M \leq \min\left(\frac{C N (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 < v_i \leq N $ - $ 1 \leq c_i \leq C $ - If $ i \neq j $ , then $ (u_i, v_i, c_i) \neq (u_j, v_j, c_j) $ - The given graph is connected. - All input values are integers.