本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：codeforces724G
正解：线性基
解题报告：
一道线性基好题…
是不是感觉和$WC2011$的那道题有相通之处呢？首先搞出一棵$dfs$树，并且得到树上每个环的$xor$值。
我们发现，两点间就是本来的$dis$ $xor$ 某些环的$xor$值，即可组合得到一些新的异或值。位运算的题目，我们显然按位来做。
首先，对于两个这一位同时为$1$或者同时为$0$的，我们考虑若要有贡献，必须是从环上得到一个这一位为$1$的$xor$值，如果线性基这一位都是$0$则无贡献，否则我们可以考虑，假设线性基中有$r$个向量，那么我们把这一位为$1$的一个向量排除在外，剩下的随便选，任意组合，也就是$2^{r-1}$，得到一个权值，再根据得到的权值这一位是$1$还是$0$，来决定被排除在外的这个向量选不选，所以贡献就是$2^{r-1}$。
同理，如果一个是$1$一个是$0$，那么我同样是分类讨论，向量中有无这一位是$1$的，分别算贡献即可。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int mod = 1000000007;
const int MAXN = 200011;
const int MAXM = 400011;
int n,m,ecnt,first[MAXN],to[MAXM],next[MAXM],scnt,dui[MAXN],cir_cnt,r;
LL dis[MAXN],w[MAXM],p[70]/*!!!不要开大了...*/,cir[MAXM],ans,fp[MAXM<<1],cnt[2];//数组不要开小了!!!
bool vis[MAXN],in[MAXN];
inline void link(int x,int y,LL z){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z; }
inline LL fast_pow(LL x,LL y){ LL r=1; while(y>0) { if(y&1) r*=x,r%=mod; x*=x; x%=mod; y>>=1; } return r; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline LL getlong(){
LL w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline void dfs(int x,LL dd,int fa){
if(dis[x]==-1) dis[x]=dd;
else {//找环
cir[++cir_cnt]=dd^dis[x];
return ;
}
vis[x]=1; dis[x]=dd; dui[++scnt]=x;
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa) continue;
dfs(v,dd^w[i],x);
}
} inline void build(){//构线性基
memset(p,0,sizeof(p)); r=0;
for(int i=1;i<=cir_cnt;i++) {
for(int j=62;j>=0;j--) {
if(!(cir[i]>>j)) continue;
if(!p[j]) { p[j]=cir[i]; break; }
cir[i]^=p[j];
}
}
for(int j=0;j<=62;j++) if(p[j]!=0) r++;//计算线性基有效的向量个数
} inline LL calc(){
build(); LL tot=0,now; bool flag;
for(int i=0;i<=62;i++) {//按位算贡献
cnt[0]=cnt[1]=0; flag=false;//是否存在某个向量的这一位为1
for(int j=0;j<=62;j++) if((p[j]>>i)&1) { flag=true; break; }
for(int j=1;j<=scnt;j++) cnt[(dis[ dui[j] ]>>i)&1]++;//统计每个dis的这一位是0还是1 now=cnt[0]*(cnt[0]-1)/2+cnt[1]*(cnt[1]-1)/2;//组合的方式记得考虑/2!!!
now%=mod;
if(flag) {
if(r>=1) now*=fp[r-1],now%=mod;
now*=fp[i],now%=mod;
tot+=now; tot%=mod;
} now=cnt[0]*cnt[1]; now%=mod;
if(flag) { if(r>=1) now*=fp[r-1],now%=mod; }
else now*=fp[r],now%=mod;
now*=fp[i],now%=mod;
tot+=now; tot%=mod;
}
return tot;
} inline void work(){
n=getint(); m=getint(); int x,y,lim=max(n,m)*2; LL z;
for(int i=1;i<=m;i++) { x=getint(); y=getint(); z=getlong(); link(x,y,z); link(y,x,z); }
fp[0]=1; for(int i=1;i<=lim;i++) fp[i]=fp[i-1]*2,fp[i]%=mod;//预处理2的整数幂
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;i++) {
if(vis[i]) continue;
scnt=0; cir_cnt=0;
dfs(i,0,0);
ans+=calc();
ans%=mod;
}
printf("%I64d",ans);
} int main()
{
work();
return 0;
}