nb题.

先任意求出一条路径,$xor$和为$x$.考虑从这条路径上出发,走到一个环$R$(其$xor$和为$w(R)$),再走回来,新的$xor$和$y=x\ xor\ w(R)$,即可以任选环.因此可以建出环的集合$S$($S$中不能包含这条路径中的边)的线性基$b(S)$,求一下$x$与$b(S)$中的数异或能得到的最大值,就是这条路径在不删掉原本的边的情况下能达到的最大$xor$和.

但要求的是所有路径中最大的$xor$和.只要稍加改进即可.
首先因为之前已说明,环可以任选,因此存在至少一条简单路径通过加环可以成为$xor$和最大的路径.
注意到,简单路径之间也可以互相转化:考虑任意两条路径$a,b$,因为其起点终点都相同,因此他们至少构成一个环.即$a$异或上这些环后,得到的异或和等于$b$的异或和.因此允许$a$异或任何环,得到的最大异或和就是答案.

考虑求环:可以用bfs/dfs,但求出的并不是所有环(如样例中的$1\rightarrow 3\rightarrow 5\rightarrow 4\rightarrow 2\rightarrow 1$这个环并没有被求出).简证一下这样不会影响正确性:
注意到,对于一条边$(u,v)$,若除了这条边之外还存在不相交的至少两条路径,设为$u\rightarrow ..\rightarrow p1\rightarrow v,u\rightarrow …\rightarrow p2\rightarrow v$
虽然$u\rightarrow ..\rightarrow p1\rightarrow v\rightarrow p2\rightarrow … \rightarrow u$这个环没有被求出,但$u\rightarrow ..\rightarrow p1\rightarrow v\rightarrow u,u\rightarrow …\rightarrow p2\rightarrow v\rightarrow u$这两个环一定会被求出,因为存在$(p1,v),(p2,v)$这两条边.这两个环异或即可得到大环.因此是正确的.因此可得求出的环数量在$\mathcal O(m)$级别.

时间复杂度$\mathcal O(m\log m)$ (我后来才意识到当有$n$个元素时,高斯消元求线性基的时间复杂度也是$\mathcal O(n\log n)$的....菜死了)

/**********/
#define MAXN 200011
#define MAXL 63
struct edge
{
    ll v,w,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
    e[++cnt]={v,w,last[u]},last[u]=cnt;
}
bool vis[MAXN];
ll dis[MAXN],a[MAXN],tot=0;
ll bfs(ll s,ll t)
{
    std::queue<ll>q;
    vis[s]=1,dis[s]=0;q.push(s);
    while(!q.empty())
    {
        ll u=q.front();q.pop();
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(!vis[v])vis[v]=1,dis[v]=dis[u]^e[i].w,q.push(v);
            else
            {
                ll k=dis[u]^dis[v]^e[i].w;
                if(k)a[++tot]=k;
            }
        }
    }
    return dis[t];
}
int main()
{
    ll n=read(),m=read();
    for(ll i=1;i<=m;++i)
    {
        ll u=read(),v=read(),w=read();
        adde(u,v,w),adde(v,u,w);
    }
    ll ans=bfs(1,n);
    for(ll i=1;i<=tot;++i)
    {
        for(ll j=i+1;j<=tot;++j)
            if(a[j]>a[i])std::swap(a[j],a[i]);
        if(!a[i]){tot=i;break;}
        for(ll k=62;k>=0;--k)
            if(a[i]&(1ll<<k))
            {
                for(ll j=1;j<=tot;++j)
                    if(j!=i&&(a[j]&(1ll<<k)))a[j]^=a[i];
                break;
            }
    }
    for(ll i=1;i<=tot;++i)
        for(ll j=62;j>=0;--j)
            if(a[i]&(1ll<<j))
            {
                if(!(ans&(1ll<<j)))ans^=a[i];
                break;
            }
    printf("%lld",ans);
    return 0;
}