You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

Output

Output minimal cycle length or -1 if it doesn't exists.

Examples

Input

3 3
1 2 1
2 3 1
3 1 1


Output

3


Input

3 2
1 2 3
2 3 4


Output

14
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static final long INF = (long) 1e15;
    static final int UNCALC = -1;
    static long[][] adjMatrix;
    static int n, targetmask;
    static long memo[];

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        n = sc.nextInt();
        adjMatrix = new long[n][n];
        long ans = 0;
        for (long[] a : adjMatrix)
            Arrays.fill(a, INF);
        int m = sc.nextInt();
        int[] degree = new int[n];
        boolean[] connectsEdge = new boolean[n];
        while (m-- > 0) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int cost = sc.nextInt();
            ans += cost;
            degree[u] = 1 - degree[u];
            degree[v] = 1 - degree[v];
            adjMatrix[u][v] = Math.min(adjMatrix[u][v], cost);
            adjMatrix[v][u] = Math.min(adjMatrix[v][u], cost);
            connectsEdge[u] = true;
            connectsEdge[v] = true;
        }
        Floyd();
        for (int i = 1; i < n; i++)
            if (connectsEdge[i] && adjMatrix[0][i] >= INF) {
                System.out.println(-1);
                return;
            }
        for (int i = 0; i < n; i++)
            System.err.println(Arrays.toString(adjMatrix[i]));
        targetmask = 0;
        for (int i = 0; i < n; i++)
            if (degree[i] == 1) targetmask |= 1 << i;
        memo = new long[1 << n];
        Arrays.fill(memo, UNCALC);
        out.println(ans + dp(0));
        out.flush();
        out.close();
    }

    static long dp(int mask) {
        if (mask == targetmask) return 0;
        if (memo[mask] != UNCALC) return memo[mask];
        long min = INF;
        for (int i = 0; i < n; i++) {
            if (!poss(i, mask)) continue;
            for (int j = i + 1; j < n; j++) {
                if (!poss(j, mask)) continue;

                min = Math.min(min, dp(mask | 1 << i | 1 << j) + adjMatrix[i][j]);
            }
        }
        return memo[mask] = min;
    }

    static boolean poss(int i, int mask) {
        return (mask & 1 << i) == 0 && (targetmask & 1 << i) != 0;
    }

    static void Floyd() {
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    adjMatrix[i][j] = Math.min(adjMatrix[i][j], adjMatrix[i][k] + adjMatrix[k][j]);
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }


        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

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

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }


        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }


        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] ans = new double[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextDouble();
            return ans;
        }

        public short nextShort() throws IOException {
            return Short.parseShort(next());
        }

    }

}