#include <iostream>
#define ll long long
#define f first
#define s second
#define inf 2000000000

using namespace std;

int n, m, nod[20][20], dp[(1<<18)+10], isOK[(1<<18)+10];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=m; i++)
        {   int nod1, nod2;
            cin >> nod1 >> nod2;
            nod[nod1][nod2] = nod[nod2][nod1] = 1;
        }
    for(int mask=1; mask<(1<<n); mask++)
        {   int cnt = 0, nrbiti = 0;
            for(int bit1=0; bit1<n; bit1++)
                if(mask & (1 << bit1))
                    {   nrbiti++;
                        for(int bit2=bit1+1; bit2<n; bit2++)
                            if(mask & (1 << bit2) && nod[bit1+1][bit2+1]) cnt++;
                    }
            if(cnt == nrbiti * (nrbiti - 1) / 2) isOK[mask] = 1;
        }
    for(int mask=1; mask<(1<<n); mask++)
        {   dp[mask] = inf;
            if(isOK[mask])
                {   dp[mask] = 1;
                    continue;
                }
            int m = mask;
            while(m)
                {   m = (m - 1) & (mask);
                    dp[mask] = min(dp[mask], dp[m] + dp[mask^m]);
                }
        }
    cout << dp[(1<<n)-1] << '\n';
    return 0;
}

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
#define itn int
#define ll long long
#define ull unsigned long long
using namespace std;

ll read(){
	ll a=0,b=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')b=-1;c=getchar();}
	while(c>='0'&&c<='9')a=a*10+c-48,c=getchar();
	return a*b;
}

const ll mod=1000000007;

ll n,ans;
struct edge{
	int v;
	ull w;
	int nx;
}e[400005];
int hd[200005],cnt;
ull xr[200005],x[200005];

void dfs(int u,int rt,ull v){
	xr[u]=v;
	for(int i=hd[u];i;i=e[i].nx){
		if(e[i].v!=rt){
			dfs(e[i].v,u,v^e[i].w);
		}
	}
}
ll r[200005][64];

int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		ull w=read();
		e[++cnt]=edge{v,w,hd[u]},hd[u]=cnt;
		e[++cnt]=edge{u,w,hd[v]},hd[v]=cnt;
	}
	dfs(1,0,0);
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<64;j++)r[i][j]=r[i-1][j];
		ull k=xr[i];
		int ct=0;
		while(k){
			r[i][ct]+=(k&1);
			k>>=1;ct++;
		}
	}
	for(int i=1;i<=n;i++){
		//cout<<i<<" :\n";
		for(int j=0;j<64;j++){
			if(xr[i]&(1ull<<j)){
				ans+=(i-1-r[i-1][j])*((1ull<<j)%mod)%mod;
				ans%=mod;
				//if(i-1-r[i-1][j])cout<<j<<' '<<ans<<'\n';
			}else{
				ans+=(r[i-1][j])*((1ull<<j)%mod)%mod;
				ans%=mod;
				//if(r[i-1][j])cout<<r[i-1][j]<<' '<<j<<' '<<ans<<'\n';
			}
		}
		//cout<<xr[i]<<' '<<ans<<'\n';
	}
	cout<<ans<<'\n';
	return 0;
}

