2 0
 6 8
1 4 1
1 5 1
1 6 1
2 4 1
2 5 1
2 6 1
3 5 1
3 6 1
 6 12
1 3 8763000
1 4 8763000
1 5 8763000
1 6 8763000
2 3 8763000
2 4 1
2 5 8763000
2 6 1
3 5 8763000
3 6 8763000
4 5 8763000
4 6 2

0
 0
 8763002

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class SolutionC extends Thread {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                                            InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    private static final FastReader scanner = new FastReader();
    private static final PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        solve();
        out.close();
    }


    static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }

    private static void solve() {
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int amountUnassigned = n * (n-1) / 2 - m;

        int[] buckets = new int[30]; //contains after reading the input one, if the bit has to be set on one edge
        int[][] matrix = new int[n][n];

        for (int i = 0; i < m; i++) {
            int ui = scanner.nextInt();
            int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            matrix[ui-1][vi-1] = wi;
            matrix[vi-1][ui-1] = wi;

            for (int j = 0; j < 30; j++) {
                if ((wi & (1 << j)) != 0) {
                    buckets[j] = 1 - buckets[j];
                }
            }
        }

        if (n >= 650) {
            out.println(0);
            return;
        }


        List<Edge> edges = new ArrayList<>(n * (n-1) / 2);
        List<Edge> unassignedEdges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                edges.add(new Edge(i, j, matrix[i][j]));
            }
        }
        Collections.sort(edges);

        int weightsToAdd = 0;
        int powTo = 1;
        for (int i = 0; i < 30; i++) {
            weightsToAdd += buckets[i] * powTo;
            powTo *= 2;
        }

        DSU dsu = new DSU(n);
        long weightMST = 0;
        long amountUnassignedUsed = 0;
        for (Edge edge: edges) {
            if (dsu.find(edge.a) != dsu.find(edge.b)) {
                dsu.union(edge.a, edge.b);
                weightMST += edge.w;
                if (edge.w == 0) {
                    amountUnassignedUsed++;
                    unassignedEdges.add(edge);
                }
            }
        }
        if (amountUnassignedUsed < amountUnassigned) {
            out.println(weightMST);
            return;
        }


        long[][] shortestPaths = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 0) {
                    shortestPaths[i][j] = matrix[i][j];
                } else {
                    shortestPaths[i][j] = Long.MAX_VALUE;
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        if (shortestPaths[i][k] != Long.MAX_VALUE && shortestPaths[k][j] != Long.MAX_VALUE) {
                            shortestPaths[i][j] = Math.min(shortestPaths[i][j], shortestPaths[i][k] + shortestPaths[k][j]);
                        }
                    }
                }
            }
        }

        long minShortcut = Long.MAX_VALUE;
        for (Edge edge: unassignedEdges) {
            minShortcut = Math.min(minShortcut, shortestPaths[edge.a][edge.b]);
        }

        out.println(weightMST + Math.min(minShortcut, weightsToAdd));
    }



    static class DSU {
        int[] leaders;
        int[] rank;
        int[] max;
        int[] min;
        int[] size;

        public DSU(int n) {
            this.leaders = new int[n];
            this.rank = new int[n];
            this.max = new int[n];
            this.min = new int[n];
            this.size = new int[n];

            for (int i = 0; i < n; i++) {
                leaders[i] = i;
                max[i] = i;
                min[i] = i;
                size[i] = 1;
                rank[i] = 0;
            }
        }

        public void union(int a, int b) {
            int aLeader = find(a);
            int bLeader = find(b);

            if (aLeader == bLeader) {
                return;
            }

            if (rank[aLeader] == rank[bLeader]) {
                rank[aLeader]++;
            }

            if (rank[aLeader] > rank[bLeader]) {
                max[aLeader] = max(max[aLeader], max[bLeader]);
                min[aLeader] = min(min[aLeader], min[bLeader]);
                size[aLeader] += size[bLeader];
                leaders[bLeader] = aLeader;
            } else {
                max[bLeader] = max(max[aLeader], max[bLeader]);
                min[bLeader] = min(min[aLeader], min[bLeader]);
                size[bLeader] += size[aLeader];
                leaders[aLeader] = bLeader;
            }
        }

        public int find(int u) {
            Stack<Integer> s = new Stack<>();
            int leader = u;
            while (leaders[leader] != leader) {
                s.push(leader);
                leader = leaders[leader];
            }
            while (!s.isEmpty()) {
                leaders[s.pop()] = leader;
            }
            return leader;
        }
    }
    //REMINDERS:
    //- CHECK FOR INTEGER-OVERFLOW BEFORE SUBMITTING

    //- CAN U BRUTEFORCE OVER SOMETHING, TO MAKE IT EASIER TO CALCULATE THE SOLUTION
}