description: There is a city park represented as a tree with n attractions as its vertices and n - 1 rails as its edges. The i-th attraction has happiness value a_i.
  
  Each rail has a color. It is either black if t_i = 0, or white if t_i = 1. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use 1 ticket.
  
  The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have k tickets, meaning you can only switch train types at most k times. In particular, you do not need a ticket to go through a path consisting of one rail color.
  
  Define f(u, v) as the sum of happiness values of the attractions in the tour (u, v), which is a simple path that starts at the u-th attraction and ends at the v-th attraction. Find the sum of f(u,v) for all valid tours (u, v) (1 ≤ u ≤ v ≤ n) that does not need more than k tickets, modulo 10^9 + 7.
  
  Input
  
  The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ n-1) — the number of attractions in the city park and the number of tickets you have.
  
  The second line contains n integers a_1, a_2,…, a_n (0 ≤ a_i ≤ 10^9) — the happiness value of each attraction.
  
  The i-th of the next n - 1 lines contains three integers u_i, v_i, and t_i (1 ≤ u_i, v_i ≤ n, 0 ≤ t_i ≤ 1) — an edge between vertices u_i and v_i with color t_i. The given edges form a tree.
  
  Output
  
  Output an integer denoting the total happiness value for all valid tours (u, v) (1 ≤ u ≤ v ≤ n), modulo 10^9 + 7.
  
  Examples
  
  Input
  
  
  5 0
  1 3 2 6 4
  1 2 1
  1 4 0
  3 2 1
  2 5 0
  
  
  Output
  
  
  45
  
  
  Input
  
  
  3 1
  1 1 1
  1 2 1
  3 2 0
  
  
  Output
  
  
  10
solution: #include <bits/stdc++.h>
  using namespace std;
  const double EPS = 1e-12;
  const int INF = 1e9 + 10;
  template <typename T>
  using MinPQ = priority_queue<T, vector<T>, greater<T>>;
  struct ModInt {
    static constexpr int MOD = 1e9 + 7;
    int v = 0;
    ModInt() {}
    ModInt(long long x) {
      v = x % MOD;
      if (v < 0) v += MOD;
    }
    friend inline bool operator==(const ModInt& l, const ModInt& r) {
      return l.v == r.v;
    }
    friend inline bool operator!=(const ModInt& l, const ModInt& r) {
      return !(l == r);
    }
    ModInt& operator+=(const ModInt& r) {
      v += r.v;
      if (v >= MOD) v -= MOD;
      return *this;
    }
    ModInt& operator-=(const ModInt& r) {
      v -= r.v;
      if (v < 0) v += MOD;
      return *this;
    }
    ModInt& operator*=(const ModInt& r) {
      v = ((long long)v * r.v) % MOD;
      return *this;
    }
    friend ModInt operator+(ModInt l, const ModInt& r) {
      l += r;
      return l;
    }
    friend ModInt operator-(ModInt l, const ModInt& r) {
      l -= r;
      return l;
    }
    friend ModInt operator*(ModInt l, const ModInt& r) {
      l *= r;
      return l;
    }
    ModInt Pow(long long n) {
      if (!n) return 1;
      ModInt r = Pow(n >> 1);
      r *= r;
      if (n & 1) r *= v;
      return r;
    }
  };
  vector<int> a;
  int max_switch;
  ModInt ans;
  struct CentroidDecomp {
    using E = int;
    int n;
    vector<vector<pair<int, E>>> adj;
    struct Node {
      int par;
      int dep;
      vector<E> up_dis;
      vector<int> child;
      int dfn;
      int last_des_dfn;
    };
    vector<Node> nodes;
    vector<int> child_idx;
    vector<int> dfsq;
    CentroidDecomp(int n = 0) { Reset(n); }
    void Reset(int n) {
      this->n = n;
      adj.assign(n, {});
    }
    void AddEdge(int u, int v, E e) {
      adj[u].emplace_back(v, e);
      adj[v].emplace_back(u, e);
    }
    void Build() {
      size.assign(n, 0);
      nodes.assign(n, Node());
      {
        int c = 0;
        int u = n + 1;
        while (u > 0) {
          ++c;
          u >>= 1;
        }
        for (int i = 0; i < n; ++i) nodes[i].up_dis.reserve(c);
      }
      DfsSize(0, -1);
      child_idx.assign(n, -1);
      dfsq.clear();
      dfsq.reserve(n);
      BuildSubtree(0, -1);
      if (0) {
        for (int i = 0; i < n; ++i) {
          Node& node = nodes[i];
          42;
        }
      }
    }
  
   private:
    vector<int> size;
    void FindCentroid(int r, int& cen, int& p_cen) {
      cen = r;
      p_cen = -1;
      bool found;
      do {
        found = 0;
        for (auto& e : (adj[cen])) {
          int v = e.first;
          if (v == p_cen || size[v] < 0) continue;
          if (size[v] * 2 >= size[r]) {
            p_cen = cen;
            cen = v;
            found = 1;
            break;
          }
        }
      } while (found);
    }
    vector<pair<int, ModInt>> tmp;
    vector<pair<int, ModInt>> f[2];
    void Dfs(int u, int pu, int sw, ModInt sum, int prev_e) {
      if (sw > max_switch) return;
      42;
      if (sw >= int((tmp).size())) {
        tmp.resize(sw + 1, {0, 0});
      }
      tmp[sw].first++;
      tmp[sw].second += sum;
      for (auto [v, e] : adj[u]) {
        if (size[v] < 0 || v == pu) continue;
        Dfs(v, u, sw + (prev_e != e), sum + a[v], e);
      }
    }
    void Com(int cen) {
      42;
      ans += a[cen];
      f[0].clear();
      f[1].clear();
      f[0].emplace_back(0, 0);
      f[1].emplace_back(0, 0);
      for (auto [u, e] : adj[cen]) {
        if (size[u] < 0) continue;
        tmp.clear();
        Dfs(u, cen, 0, ModInt(a[u]), e);
        for (int i = 0; i < int((tmp).size()); ++i) {
          int mf = min(max_switch - i, int((f[e]).size()) - 1);
          if (mf >= 0)
            ans += tmp[i].second * f[e][mf].first +
                   f[e][mf].second * tmp[i].first +
                   ModInt(a[cen]) * tmp[i].first * f[e][mf].first;
          mf = min(max_switch - i - 1, int((f[1 - e]).size()) - 1);
          if (mf >= 0)
            ans += tmp[i].second * f[1 - e][mf].first +
                   f[1 - e][mf].second * tmp[i].first +
                   ModInt(a[cen]) * tmp[i].first * f[1 - e][mf].first;
        }
        {
          int sz = max(int((tmp).size()), int((f[e]).size()));
          if (sz > int((f[e]).size())) f[e].resize(sz, f[e].back());
          if (sz > int((tmp).size())) tmp.resize(sz, {0, 0});
          for (int i = 0; i < sz; ++i) {
            if (i > 0) {
              tmp[i].first += tmp[i - 1].first;
              tmp[i].second += tmp[i - 1].second;
            }
            f[e][i].first += tmp[i].first;
            f[e][i].second += tmp[i].second;
          }
        }
      }
      42;
      ans += f[0].back().second + ModInt(a[cen]) * f[0].back().first;
      ans += f[1].back().second + ModInt(a[cen]) * f[1].back().first;
      42;
    }
    void BuildSubtree(int r, int pr) {
      42;
      int cen;
      {
        int p_cen;
        FindCentroid(r, cen, p_cen);
        nodes[cen].par = pr;
        nodes[cen].dep = (pr < 0) ? 0 : nodes[pr].dep + 1;
        Com(cen);
        size[cen] = -1;
        if (p_cen >= 0 && size[p_cen] >= 0) DfsSize(p_cen, -1);
      }
      nodes[cen].dfn = int((dfsq).size());
      dfsq.push_back(cen);
      if (pr >= 0) {
        child_idx[cen] = int((nodes[pr].child).size());
        nodes[pr].child.push_back(cen);
      }
      42;
      for (auto& e : (adj[cen])) {
        int v = e.first;
        if (size[v] < 0) continue;
        BuildSubtree(v, cen);
      }
      nodes[cen].last_des_dfn = int((dfsq).size()) - 1;
    }
    void DfsSize(int u, int pu) {
      size[u] = 1;
      for (auto& e : (adj[u])) {
        int v = e.first;
        if (v == pu || size[v] < 0) continue;
        DfsSize(v, u);
        size[u] += size[v];
      }
    }
    void DfsDis(int u, int pu, E sum_e) {
      nodes[u].up_dis.push_back(sum_e);
      for (auto& e : (adj[u])) {
        int v = e.first;
        if (v == pu || size[v] < 0) continue;
        DfsDis(v, u, sum_e + e.second);
      }
    }
  };
  CentroidDecomp cd;
  void Solve() {
    int n;
    scanf("%d%d", &n, &max_switch);
    a.resize(n);
    for (auto& x : (a)) scanf("%d", &x);
    cd.Reset(n);
    for (int i = 1; i < n; ++i) {
      int u, v, e;
      scanf("%d%d%d", &u, &v, &e);
      --u;
      --v;
      cd.AddEdge(u, v, e);
    }
    ans = 0;
    cd.Build();
    printf("%d\n", ans.v);
  }
  int main() {
    int t = 1;
    for (int i = 1; i <= t; ++i) {
      Solve();
    }
    return 0;
  }
  