没时间写了，有空补。

考虑先生成出来一个最小生成树。

注意到，若想替换一些边后使得生成树仍最小，必须替换边权相同的边。

因此，对于每个边权 $u$，枚举选择哪些边可以使图仍然连通（UPD：应该判仍然无环）。

复杂度 $\mathcal O\left(2^{k}m\right)$。

UPDATE：补完了。

#include <bits/stdc++.h>
using namespace std;

static constexpr uint32_t mod = 31011;

struct Dsu {
  vector<uint32_t> fa, sz;
  stack<uint32_t> hist;

  Dsu(uint32_t n) : fa(n), sz(n, 1) { iota(fa.begin(), fa.end(), 0); }

  uint32_t find(uint32_t x) {
    while (x != fa[x])
      x = fa[x];
    return x;
  }

  bool unite(uint32_t x, uint32_t y) {
    x = find(x), y = find(y);
    if (x == y)
      return false;
    if (sz[x] < sz[y])
      swap(x, y);
    hist.emplace(y);
    fa[y] = x, sz[x] += sz[y];
    return true;
  }

  bool undo() {
    if (hist.empty())
      return false;
    uint32_t y = hist.top();
    hist.pop();
    uint32_t x = fa[y];
    fa[y] = y, sz[x] -= sz[y];
    return true;
  }
};

uint32_t dfs_no_circle(vector<tuple<uint32_t, uint32_t, uint64_t>> &edges, uint32_t cur,
                       uint32_t end, uint32_t k, Dsu &dsu) {
  if (end - cur < k)
    return 0;
  if (k == 0)
    return 1;
  uint32_t ans = 0;
  for (uint32_t i = cur; i <= end - k; ++i) {
    const auto &[u, v, _] = edges[i];
    if (dsu.unite(u, v)) {
      (ans += dfs_no_circle(edges, i + 1, end, k - 1, dsu)) %= mod;
      dsu.undo();
    }
  }
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  uint32_t n, m;
  cin >> n >> m;

  vector<tuple<uint32_t, uint32_t, uint64_t>> edges;
  edges.reserve(m);

  for (uint32_t i = 0; i < m; ++i) {
    uint32_t u, v;
    uint64_t w;
    cin >> u >> v >> w, --u, --v;
    edges.emplace_back(u, v, w);
  }
  sort(edges.begin(), edges.end(),
       [](const auto &a, const auto &b) { return get<2>(a) < get<2>(b); });

  Dsu dsu(n);
  uint32_t edge_cnt = 0;
  uint64_t ans = 1;
  for (uint32_t i = 0, j; i < m; i = j) {
    j = i + 1;

    while (j < m && get<2>(edges[j]) == get<2>(edges[i]))
      ++j;

    uint32_t used = 0;
    for (uint32_t k = i; k < j; ++k) {
      const auto &[u, v, _] = edges[k];
      if (dsu.unite(u, v))
        ++used;
    }

    for (uint32_t k = 0; k < used; ++k)
      dsu.undo();
    (ans *= dfs_no_circle(edges, i, j, used, dsu)) %= mod;

    for (uint32_t k = i; k < j; ++k) {
      const auto &[u, v, _] = edges[k];
      dsu.unite(u, v);
    }
    edge_cnt += used;
  }

  if (edge_cnt != n - 1)
    ans = 0;

  cout << ans << '\n';

  return 0;
}