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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D {

    static final int INF = Integer.MAX_VALUE / 3;

    int[][] e;
    boolean[] odd;
    int n;
    int best = INF;

    public static void main(String[] args) throws IOException {
        new D().solve();
    }

    BufferedReader br;
    StringTokenizer st = new StringTokenizer("");

    private void solve() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        this.n = nextInt();
        int m = nextInt();
        this.e = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(e[i], INF);
            e[i][i] = 0;
        }
        int sumW = 0;
        boolean[] withEdges = new boolean[n];
        int[] deg = new int[n];
        for (int i = 0; i < m; i++) {
            int a = nextInt() - 1;
            int b = nextInt() - 1;
            int w = nextInt();
            sumW += w;
            e[a][b] = Math.min(e[a][b], w);
            e[b][a] = e[a][b];
            deg[a]++;
            deg[b]++;
            withEdges[a] = withEdges[b] = true;
        }
        this.odd = new boolean[n];
        for (int i = 0; i < n; i++) {
            this.odd[i] = deg[i] % 2 == 1;
        }
        br.close();

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

        boolean ok = true;
        for (int i = 0; i < n; i++) {
            if (withEdges[i] && e[0][i] == INF) {
                ok = false;
                break;
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        if (ok) {
            rec(0, 0);
            pw.println(sumW + best);
        } else {
            pw.println(-1);
        }
        pw.close();
    }

    private void rec(final int k, final int cur) {
        if (k == n) {
            best = Math.min(best, cur);
            return;
        }
        if (!odd[k]) {
            rec(k + 1, cur);
            return;
        }
        for (int i = k + 1; i < n; i++) {
            if (odd[i]) {
                odd[k] = false;
                odd[i] = false;
                rec(k + 1, cur + e[k][i]);
                odd[k] = true;
                odd[i] = true;
            }
        }
    }

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

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