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.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class ChineesePostman {

    static int[][] w;
    static int[][] g;
    static int[] oddm;
    static int n;
    static int[] oddCount;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        if (m == 0) {
            System.out.println("0");
            return;
        }
        w = new int[n][n];
        g = new int[n][n];
        oddCount = new int[n];
        int odd = 0;
        long result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = Integer.MAX_VALUE;
                w[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt() - 1;
            int to = sc.nextInt() - 1;
            int ww = sc.nextInt();
            g[from][to] = Math.min(g[from][to], ww);
            g[to][from] = Math.min(g[from][to], ww);
            oddCount[from] += 1;
            oddCount[to] += 1;
            result += ww;
        }
        for (int i = 0; i < n; i++) {
            if (oddCount[i] % 2 == 1) {
                odd += 1;
            }
        }
        oddm = new int[odd];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (oddCount[i] % 2 != 0) {
                oddm[cnt] = i;
                cnt++;
            }
        }
        if (!countW()) {
            System.out.println("-1");
            return;
        }
        int[] dp = new int[1 << odd];
        dp[0] = 0;
        for (int i = 1; i < 1 << odd; i++) {
            dp[i] = Integer.MAX_VALUE / 2;
            int l = last(i) - 1;
            if (cnt(i) % 2 == 0) {
                for (int p = 0; p < l; p++) {
                    if (set(i, p)) {
                        int x = (i ^ (1 << p)) ^ (1 << l);
                        dp[i] = Math.min(dp[i], dp[x] + minw(l, p));
                    }
                }
            } else {
                for (int p = 0; p < l; p++) {
                    if (set(i, p)) {
                        int x = i ^ (1 << l);
                        dp[i] = Math.min(dp[i], dp[x] + minw(l, p));
                    }
                }
            }
        }
        result += dp[(1 << odd) - 1];
        System.out.println(result);
    }

    static int last(int n) {
        int r = 0;
        while (n > 0) {
            n >>= 1;
            r += 1;
        }
        return r;
    }

    static int cnt(int n) {
        int r = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                r += 1;
            }
            n >>= 1;
        }
        return r;
    }

    static boolean set(int i, int b) {
        return (i & (1 << b)) > 0;
    }

    static boolean countW() {
        for (int i = 0; i < n; i++) {
            int[] curw = new int[n];
            for (int j = 0; j < n; j++) {
                curw[j] = Integer.MAX_VALUE;
            }
            boolean[] visited = new boolean[n];
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Integer.compare(curw[o1], curw[o2]);
                }
            });
            pq.add(i);
            curw[i] = 0;
            while (!pq.isEmpty()) {
                int cur = pq.poll();
                if (!visited[cur]) {
                    visited[cur] = true;
                    for (int k = 0; k < n; k++) {
                        if (g[cur][k] != Integer.MAX_VALUE) {
                            curw[k] = Math.min(curw[k], curw[cur] + g[cur][k]);
                            pq.add(k);
                        }
                    }
                }
            }
            w[i] = curw;
            if (i == 0) {
                for (int k = 0; k < n; k++) {
                    if (curw[k] == Integer.MAX_VALUE && oddCount[k] > 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    static int minw(int from, int to) {
        int f = oddm[from];
        int t = oddm[to];
        return w[f][t];
    }

}
