Language: C++

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1000000007;

using Long = long long;
template<typename T>
using V = vector<T>;
template<typename T>
using Vv = V<V<T>>;
using Vb = V<bool>;
using Vvb = V<Vb>;
using Vi = V<int>;
using Vvi = V<Vi>;
using Vl = V<Long>;
using Vvl = V<Vl>;
using Vd = V<double>;
using Vvd = V<Vd>;
using Vs = V<string>;

template <typename T>
istream& operator>>(istream& is, const vector<T>& v) {
    for (auto& x : v) {
        is >> x;
    }
    return is;
}

template <typename First, typename Second>
istream& operator>>(istream& is, const pair<First, Second>& v) {
    return is >> v.first >> v.second;
}

class UnionFind {
public:
    explicit UnionFind(int size) : data(size, -1), numUnions{size} {}

    int getNumUnions() {
        return numUnions;
    }

    int getUnionSize(int u) {
        return -data[find(u)];
    }

    bool isUnited(int u, int v) {
        return find(u) == find(v);
    }

    struct UniteResult {
        int root;
        bool united;
    };

    UniteResult unite(int u, int v) {
        int uRoot = find(u);
        int vRoot = find(v);
        if (uRoot == vRoot) {
            return {uRoot, false};
        }
        int uSize = data[uRoot];
        int vSize = data[vRoot];
        if (uSize > vSize) {
            swap(uRoot, vRoot);
            swap(uSize, vSize);
        }
        data[uRoot] += vSize;
        data[vRoot] = uRoot;
        numUnions--;
        return {uRoot, true};
    }

    int find(int u) {
        assert(u >= 0 && u < data.size());
        while (true) {
            int p = data[u];
            if (p < 0) {
                return u;
            }
            int gp = data[p];
            if (gp < 0) {
                return p;
            }
            u = data[u] = gp;
        }
    }

private:
    vector<int> data;
    int numUnions;
};

// *** SOLUTION BEGIN ***

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    vector<pair<int, pair<int, int>>> edges(m);
    for (auto& e : edges) {
        cin >> e.second >> e.first;
        e.second.first--;
        e.second.second--;
    }
    sort(begin(edges), end(edges));
    int countLess = 0;
    int countEqual = 0;
    int countGreater = 0;
    for (const auto& e : edges) {
        UnionFind uf{n};
        uf.unite(e.second.first, e.second.second);
        Long w = e.first;
        for (const auto& ee : edges) {
            if (uf.unite(ee.second.first, ee.second.second).united) {
                w += ee.first;
            }
        }
        if (w < x) {
            countLess++;
        } else if (w == x) {
            countEqual++;
        } else {
            countGreater++;
        }
    }
    auto pow = [](int x, int y) {
        Long res = 1;
        while (y--) {
            res *= x;
            res %= MOD;
        }
        return res;
    };
    if (countLess) {
        cout << 2 * (pow(2, countEqual) + MOD - 1LL) * pow(2, countGreater) % MOD;
    } else if (countEqual) {
        cout << (pow(2, countEqual) + MOD - 2LL) * pow(2, countGreater) % MOD;
    } else {
        cout << 0;
    }
}

// *** SOLUTION END ***

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    cout << fixed;
    solve();
    return 0;
}


Compiler output:
a.cc: In instantiation of 'std::istream& operator>>(std::istream&, const std::pair<_T1, _T2>&) [with First = int; Second = int; std::istream = std::basic_istream<char>]':
a.cc:101:18:   required from here
  101 |         cin >> e.second >> e.first;
      |                  ^~~~~~
a.cc:32:15: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'const int')
   32 |     return is >> v.first >> v.second;
      |            ~~~^~~~~~~~~~
In file included from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127,
                 from a.cc:1:
/usr/include/c++/14/istream:170:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'bool&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:174:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'short int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:177:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:184:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'unsigned int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:188:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'long int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:192:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:192:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:199:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:203:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  203 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:203:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:219:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  219 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:219:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'float&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:223:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  223 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:223:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'double&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:227:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  227 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:227:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: cannot bind non-const lvalue reference of type 'long double&' to a value of type 'int'
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
/usr/include/c++/14/istream:328:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  328 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/14/istream:328:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: invalid conversion from 'int' to 'void*' [-fpermissive]
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
      |                    |
      |                    int
a.cc:32:20: error: cannot bind rvalue '(void*)((long int)((int)v.std::pair<int, int>::first))' to 'void*&'
/usr/include/c++/14/istream:122:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(__istream_type& (*)(__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  122 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/14/istream:122:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: invalid conversion from 'int' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
      |                    |
      |                    int
/usr/include/c++/14/istream:126:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(__ios_type& (*)(__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>; __ios_type = std::basic_ios<char>]' (near match)
  126 |       operator>>(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/14/istream:126:7: note:   conversion of argument 1 would be ill-formed:
a.cc:32:20: error: invalid conversion from 'int' to 'std::basic_istream<char>::__ios_type& (*)(std::basic_istream<char>::__ios_type&)' {aka 'std::basic_ios<char>& (*)(std::basic_ios<char>&)'} [-fpermissive]
   32 |     return is >> v.first >> v.second;
      |                  ~~^~~~~
      |                    |
      |                    int
/usr/include/c++/14/istream:133:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near