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

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
//#define ld long double
#define mod 1000000007
//define inf 100000000000010
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
//#define INF LONG_MAX
#define PI 3.1415926535897932384626
//#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define repr(x,n,j)for(ll x=n;x>j;x--)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pi;
typedef long double ld;

mt19937 myrand(time(0));

bool isprime(ll n)
{
    if(n<=1)return false;
    if(n<=3)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
}

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}




ll builtin_popcount(ll x)
{
    ll cnt = 0;
    for(ll i=60;i>=0;i--)
    {
        if((1LL<<i)&x)cnt++;
    }
    return cnt;
}

ll addmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a+b)%mod;
}
ll mulmod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    return (a*b)%mod;
}
ll submod(ll a,ll b)
{
    a%=mod;
    b%=mod;
    a-=b;
    if(a<0)a+=mod;
    return a%mod;
}


struct CustomCompare
{
    bool operator()(pi a,pi b)
    {
        return a.fi<b.fi;
    }
};
/*
const int mxn = 5*(1e6) +10;
vi spf(mxn);
void sieve()
{
    for(ll i =0;i<mxn;i++)spf[i]  = i;
    for(ll i=2;i<mxn;i+=2)spf[i] = 2;
    for(ll i = 3;i*i<mxn;i++)
    {
        if(spf[i]==i)
        {
            for(ll j = i*i;j<mxn;j+=i)
            {
                if(spf[j]==j)spf[j] = i;
            }
        }
    }
}
*/

const int mxn = 18;

ll adj[mxn][mxn];

bool check[(1LL<<mxn)];
ll dp[(1LL<<mxn)];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

ll n,m; cin>>n>>m;

rep(i,0,m)
{
    ll x,y; cin>>x>>y;
    --x,--y;
    adj[x][y] = adj[y][x] = 1;
}

//cout<<"ok"<<endl;
rep(i,1LL,1LL<<n)
{
    vi arr;
    rep(j,0,n)if((1LL<<j)&i)arr.pb(j);

    check[i] = true;
    ll sz = arr.size();
    rep(j,0,sz)
    {
        rep(k,j+1,sz)
        {
            ll x = arr[j] ,y = arr[k];
            if(!adj[x][y]&&!adj[y][x])check[i] = false;
        }
    }
}
//cout<<"ok"<<endl;
rep(i,1LL,1LL<<n)dp[i] = 1e10;
dp[0] = 0;

rep(i,1LL,1LL<<n)
{
    if(check[i])dp[i] = 1;
    for(ll j=i;j;j=(j-1LL)&i)dp[i] = min(dp[i],dp[j]+dp[i^j]);
}
cout<<dp[(1LL<<n)-1];
return 0;

}
/*
1
4 7
...*...
..***..
.****..
*******


*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define endl '\n'
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define done(x) {cout << x << endl;return;}
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//const int mod = 998244353;
const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
typedef map<int, int> mii;
typedef set<int> si;
typedef set<pair<int,int>> spii;
typedef queue<int> qi;
uniform_int_distribution<int> rng(0, 1e9);

//DEBUG FUNCTIONS START
#define cerr cout
void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define deb(x...)  _print(x)
#else
#define deb(x...)
#endif
// DEBUG FUNCTIONS END


const int N = 2e5 + 5;
vpii g[N];
int f[60][2];


void dfs(int v, int p, int msk){

    rep(i,0,60){
        f[i][msk >> i & 1]++;
    }

    for(auto [to, w] : g[v]){
        if(to != p){
            dfs(to, v, msk ^ w);
        }
    }


}

int powm(int a, int b){
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}



void solve(){
    
    
    int n;
    cin >> n;

    fr(i,2,n){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    dfs(1, 1, 0);

    int ans = 0;

    rep(i,0,60){
            ans += (1ll << i) % mod * f[i][0] % mod * f[i][1] % mod;
            ans %= mod;
    }

    cout << ans << endl;

}




signed main() {

    #ifdef LOCAL
        (void)!freopen("input.txt","r",stdin);
        (void)!freopen("output.txt","w",stdout);
    #endif
    
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;

    while (t--)
        solve();
    return 0;
}



int divide(int a, int b) {
    return (a % mod) * powm(b % mod, mod - 2) % mod;
}

