Codefroces Educational Round 27 845G Shortest Path Problem?

You are given an undirected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times). You have to find the minimum length of path between vertex 1 and vertex n.

Note that graph can contain multiple edges and loops. It is guaranteed that the graph is connected.

Input

The first line contains two numbers n and m (1 ≤ n ≤ 100000, n - 1 ≤ m ≤ 100000) — the number of vertices and the number of edges, respectively.

Then m lines follow, each line containing three integer numbers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸). These numbers denote an edge that connects vertices x and y and has weight w.

Output

Print one number — the minimum length of path between vertices 1 and n.

Examples

Input

Output

Input

2 2
1 1 3
1 2 3

Output

0
最短路，取异或值最小，并且每一个点可以重复经过，dfs搜索，没经过的点扩展路径，经过的点更新异或值。

#include <iostream> 
#include <algorithm> 
#include <cstring> 
#include <cstdio>
#include <vector> 
#include <queue> 
#include <stack>
#include <cstdlib> 
#include <iomanip>
#include <cmath>//自定义最小函数取不了过去，会有影响，所以用了库函数
#include <cassert>
#include <ctime> 
#include <map> 
#include <set> 
using namespace std; 
#define lowbit(x) (x&(-x))  
#define MAX 100000000000000000 
#define MOD 1000000007
#define pi acos(-1.0) 
#define ei exp(1) 
#define PI 3.141592653589793238462
#define ios() ios::sync_with_stdio(false)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
vector<pair<int,int> >v[100006];
vector<int>uxor;
int dis[100006],vis[100006];
int n,m,x,y,w;
void updatexor(int u)
{
    for(int i=0;i<uxor.size();i++)
    {
        u=min(u,u^uxor[i]);
    }
    if(u) uxor.push_back(u);
}
void dfs(int u,int result)
{
    vis[u]=1;
    dis[u]=result;
    for(int i=0;i<v[u].size();i++)
    {
        if(!vis[v[u][i].first]) dfs(v[u][i].first,dis[u]^v[u][i].second);
        else updatexor(dis[u]^v[u][i].second^dis[v[u][i].first]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        v[x].push_back(make_pair(y,w));
        v[y].push_back(make_pair(x,w));
    }
    memset(vis,0,sizeof(vis));
    dfs(1,0);
    for(int i=0;i<uxor.size();i++)
    {
        dis[n]=min(dis[n],dis[n]^uxor[i]);
    }
    printf("%d
",dis[n]);
    return 0;
}