As a teacher, Riko Hakozaki often needs to help her students with problems from various subjects. Today, she is asked a programming task which goes as follows.

You are given an undirected complete graph with n nodes, where some edges are pre-assigned with a positive weight while the rest aren't. You need to assign all unassigned edges with non-negative weights so that in the resulting fully-assigned complete graph the [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) sum of all weights would be equal to 0.

Define the ugliness of a fully-assigned complete graph the weight of its [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree), where the weight of a spanning tree equals the sum of weights of its edges. You need to assign the weights so that the ugliness of the resulting graph is as small as possible.

As a reminder, an undirected complete graph with n nodes contains all edges (u, v) with 1 ≤ u < v ≤ n; such a graph has (n(n-1))/(2) edges.

She is not sure how to solve this problem, so she asks you to solve it for her.

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ min(2 ⋅ 10^5, (n(n-1))/(2) - 1)) — the number of nodes and the number of pre-assigned edges. The inputs are given so that there is at least one unassigned edge.

The i-th of the following m lines contains three integers u_i, v_i, and w_i (1 ≤ u_i, v_i ≤ n, u ≠ v, 1 ≤ w_i < 2^{30}), representing the edge from u_i to v_i has been pre-assigned with the weight w_i. No edge appears in the input more than once.

Output

Print on one line one integer — the minimum ugliness among all weight assignments with XOR sum equal to 0.

Examples

Input


4 4
2 1 14
1 4 14
3 2 15
4 3 8


Output


15


Input


6 6
3 6 4
2 4 1
4 5 7
3 4 10
3 5 1
5 2 15


Output


0


Input


5 6
2 3 11
5 3 7
1 4 10
2 4 14
4 3 8
2 5 6


Output


6

Note

The following image showcases the first test case. The black weights are pre-assigned from the statement, the red weights are assigned by us, and the minimum spanning tree is denoted by the blue edges.

<image>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 20;
vector<int> g[N];
vector<pair<ll, pair<int, int>>> edges;
ll bal, ans;

bool vis[N];
set<int> unvis;

int p[N], p2[N], cnt[N], sz[N];

int root(int v){
  if(p[v] == v)
    return v;
  return p[v] = root(p[v]);
}

void merge(int a, int b){
  a = root(a);
  b = root(b);
  if(a == b)
    return;
  p[b] = a;
  sz[a] += sz[b];
}

int root2(int v){
  if(p2[v] == v)
    return v;
  return p2[v] = root2(p2[v]);
}

void merge2(int a, int b){
  a = root2(a);
  b = root2(b);
  if(a == b)
    return;
  p2[b] = a;
}

queue<int> q;
void bfs(int s){
  q.push(s);
  vis[s] = true;
  unvis.erase(s);
  while(!q.empty()){
    int v = q.front();
    q.pop();
    for(int x : g[v])
      if(!vis[x])
        unvis.erase(x);
    for(int x : unvis){
      merge(v, x);
      q.push(x);
      vis[x] = true;
    }
    unvis.clear();
    for(int x : g[v])
      if(!vis[x])
        unvis.insert(x);
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < m; i ++){
    int u, v; ll w;
    cin >> u >> v >> w;
    u --; v --;
    g[v].push_back(u);
    g[u].push_back(v);
    edges.push_back({w, {u, v}});
    bal ^= w;
  }
  for(int i = 0; i < n; i ++){
    unvis.insert(i);
    p[i] = i;
    sz[i] = 1;
    p2[i] = i;
  }
  for(int i = 0; i < n; i ++){
    if(!vis[i])
      bfs(i);
  }
  bool ok = false;
  for(int i = 0; i < m; i ++){
    auto [x, y] = edges[i].second;
    if(root(x) == root(y)){
      cnt[root(x)] ++;
      bal = min(bal, edges[i].first);
    }
  }
  for(int i = 0; i < n; i ++){
    int x = root(i);
    if(sz[x] * (ll)(sz[x] - 1) / 2LL - cnt[x] - sz[x] + 1 > 0)
      ok = true;
  }
  sort(edges.begin(), edges.end());
  for(int i = 0; i < m; i ++){
    auto [x, y] = edges[i].second;
    if(root(x) != root(y)){
      ans += edges[i].first;
      merge(x, y);
      merge2(x, y);
    }
  }
  for(int i = 0; i < m; i ++){
    auto [x, y] = edges[i].second;
    if(root2(x) != root2(y))
      bal = min(bal, edges[i].first);
  }
  if(!ok)
    ans += bal;
  cout << ans;
}
